Mastering Algorithms for Problem Solving in C++/

...

/

Relax ALL the Edges: Bellman-Ford

Relax ALL the Edges: Bellman-Ford

Get to know the Bellman-Ford algorithm and its applications in solving the shortest paths problem.

We'll cover the following...

Understanding of Bellman-Ford algorithm

The simplest implementation of Ford’s generic shortest-path algorithm was first sketched by Alfonso Shimbel in 1954, described in more detail by Edward Moore in 1957, and independently rediscovered by Max Woodbury and George Dantzig in 1957, by Richard Bellman in 1958, and by George Minty in 1958. (Neither Woodbury and Dantzig nor Minty published their algorithms.) In full compliance with Stigler’s Law, the algorithm is almost universally known as Bellman-Ford, because Bellman explicitly used Ford’s 1956 formulation of relaxing edges, although some authors refer to Bellman-Kalaba and a few early sources refer to Bellman-Shimbel.

The images below show a complete run of Dijkstra’s algorithm on a graph with negative edges. At each iteration, bold edges indicate predecessors; shaded vertices are in the priority queue; and the bold vertex is the next to be scanned.

The Shimbel / Moore / Woodbury-Dantzig / Bellman-Ford / Kalaba / Minty / Brosh algorithm can be summarized in one line:

  • Bellman-Ford: Relax ALL the tense edges, then recurse.

Algorithm

BellmanFord(s)‾InitSSSP(s)while there is at least one tense edgefor every edge u→vif u→v is tenseRelax(u→v)\underline{BellmanFord(s)} \\ \hspace{0.4cm} InitSSSP(s) \\ \hspace{0.4cm} while\space there\space is\space at\space least\space one\space tense\space edge \\ \hspace{1cm} for\space every\space edge\space u\rightarrow v \\ \hspace{1.7cm} if\space u\rightarrow v\space is\space tense \\ \hspace{2.3cm} Relax(u\rightarrow v)

Implementation

C++
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// Graph data structure
const int MAX_V = 1000;	// Maximum number of vertices
vector<pair<int, int>> adj[MAX_V];	// Adjacency list of edges
// Bellman-Ford algorithm
int dist[MAX_V];	// Shortest distance from source vertex
bool tense[MAX_V];	// Whether a vertex has been updated during the current iteration
void InitSSSP(int s)
{
	// Initialize shortest path distances
	for (int i = 0; i < MAX_V; i++)
	{
		dist[i] = INT_MAX;
	}
	dist[s] = 0;
	tense[s] = true;
}
bool HasTenseEdge()
{
	// Check if there is at least one tense edge
	for (int u = 0; u < MAX_V; u++)
	{
		if (tense[u])
		{
			return true;
		}
	}
	return false;
}
void Relax(int u, int v, int weight)
{
	// Relax the edge (u, v)
	if (dist[u] != INT_MAX && dist[v] > dist[u] + weight)
	{
		dist[v] = dist[u] + weight;
		tense[v] = true;
	}
}
void BellmanFord(int s)
{
	// Initialize single source shortest path
	InitSSSP(s);
	// Loop until no more tense edges exist
	while (HasTenseEdge())
	{
		// Iterate through all edges
		for (int u = 0; u < MAX_V; u++)
		{
			for (int i = 0; i < adj[u].size(); i++)
			{
				int v = adj[u][i].first;
				int weight = adj[u][i].second;
				// Relax the edge if it is tense
				if (tense[u] && tense[v])
				{
					Relax(u, v, weight);
				}
			}
			tense[u] = false;
		}
	}
}
int main()
{
	// Build example graph
	adj[0].push_back(make_pair(1, 5));
	adj[1].push_back(make_pair(2, 2));
	adj[2].push_back(make_pair(3, 3));
	adj[3].push_back(make_pair(4, -4));
	adj[4].push_back(make_pair(1, 1));
	// Run Bellman-Ford algorithm from source vertex 0
	BellmanFord(0);
	// Print shortest distances from source vertex
	for (int i = 0; i < MAX_V; i++)
	{
		cout << "Shortest distance from vertex 0 to " << i << " is " << dist[i] << endl;
	}
	return 0;
}

Explanation

  • Lines 14–24: The code initializes the shortest path distances from the source vertex to all other vertices. The distance to all vertices is set to a large value (INT_MAX), except for the source vertex, which has a distance of 0. The tense array is also initialized to true for the source vertex, since it has been updated during the first iteration of the algorithm.

  • Lines 26–38: The code checks if there is at least one tense edge in the graph.

  • Lines 40–48: The Relax function updates the shortest distance to vertex v if a shorter path through vertex u is found. This function is called for each edge in the graph during each iteration of the algorithm.

  • Lines 56–75: The code finds the shortest path from a source vertex to all other vertices in a weighted directed graph. It initializes the shortest path distances, relaxes the edges to update the shortest paths, and repeats this process until there are no more tense edges.

  • Lines 91–94: The code prints the shortest distances from the source vertex.

The following lemma is the key to proving both the correctness and efficiency of Bellman-Ford. For every vertex vv and non-negative integer ii, let dist≤i(v)dist≤i(v) denote the length of the shortest walk in GG from ss to vv, consisting of at most ii edges. In particular, dist≤0(s)=0dist≤_0(s) = 0 and dist≤0(v)=∞dist≤_0(v) = ∞ for all v≠sv \neq s.

Lemma 1: For every vertex vv and non-negative integer ii, after ii iterations of the main loop of BellmanFordBellmanFord, we have dist(v)≤dist≤i(v)dist(v) ≤ dist≤_i(v).

Proof: The proof proceeds by induction on ii. The base case i=0i = 0 is trivial, so assume i>0i > 0. Fix a vertex vv, and let WW be the shortest walk from ss to vv, consisting of at most ii edges (breaking ties arbitrarily). By definition, WW has length dist≤i(v)dist≤_i(v). There are two cases to consider.

  • Suppose WW has no edges. Then, WW must be the trivial walk from ss to ss, so v=sv = s and dist≤i(s)=0dist≤_i(s) = 0. We set dist(s)←0dist(s) ← 0 in InitSSSPInitSSSP, and dist(s)dist(s) can never increase, so we always have dist(s)≤0dist(s) ≤ 0.
  • Otherwise, let u→vu\rightarrow v be the last edge of WW. The induction hypothesis implies that after i−1i − 1 iterations, dist(u)≤dist≤i−1(u)
...