Mastering Algorithms for Problem Solving in Python/

...

/

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.”

Below is 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

Press + to interact
import sys
# Graph data structure
MAX_V = 1000	# Maximum number of vertices
adj = [[] for _ in range(MAX_V)]	# Adjacency list of edges
# Bellman-Ford algorithm
dist = [sys.maxsize] * MAX_V	# Shortest distance from source vertex
tense = [False] * MAX_V	# Whether a vertex has been updated during the current iteration
def InitSSSP(s):
    # Initialize shortest path distances
    for i in range(MAX_V):
        dist[i] = sys.maxsize
    dist[s] = 0
    tense[s] = True
def HasTenseEdge():
    # Check if there is at least one tense edge
    for u in range(MAX_V):
        if tense[u]:
            return True
    return False
def Relax(u, v, weight):
    # Relax the edge (u, v)
    if dist[u] != sys.maxsize and dist[v] > dist[u] + weight:
        dist[v] = dist[u] + weight
        tense[v] = True
def BellmanFord(s):
    # Initialize single source shortest path
    InitSSSP(s)
    # Loop until no more tense edges exist
    while HasTenseEdge():
        # Iterate through all edges
        for u in range(MAX_V):
            for i in range(len(adj[u])):
                v = adj[u][i][0]
                weight = adj[u][i][1]
                # Relax the edge if it is tense
                if tense[u] and tense[v]:
                    Relax(u, v, weight)
            tense[u] = False
if __name__ == '__main__':
    # Build example graph
    adj[0].append((1, 5))
    adj[1].append((2, 2))
    adj[2].append((3, 3))
    adj[3].append((4, -4))
    adj[4].append((1, 1))
    # Run Bellman-Ford algorithm from source vertex 0
    BellmanFord(0)
    # Print shortest distances from source vertex
    for i in range(MAX_V):
        print(f"Shortest distance from vertex 0 to {i} is {dist[i]}")

Explanation

  • Line 5: We create an adjacency list to store the edges in the graph. The list is initialized as an empty list for each vertex.

  • Line 8: We initialize the distances to each vertex with the maximum value of an integer.

  • Line 11: This function initializes the distances and tense lists for the source vertex s.

  • Line 33: This function implements the Bellman-Ford algorithm by initializing the distances and tense lists for the source vertex and then iterating through all edges until no more tense edges exist. For each edge, it checks if it is tense and relaxes it if it can be improved. After each iteration, it marks all the vertices as not tense.

  • Lines 63–64: We iterate through all vertices and print the shortest distance from vertex 0 to each 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: For every vertex vv and non-negative integer ii, after ii iterations of the main loop of Bellman-Ford, 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 since dist(s)dist(s) can never increase, 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)dist(u) ≤ dist≤_{i−1}(u)
...