• Bellman-Ford Algorithm
  • Single Source Shortest Path
  • Negative Cycle Detection

Bellman-Ford Algorithm

Single Source Shortest Path

The Bellman-Ford algorithm allows us to find the shortest paths with arbitrary edge weights. We decrease $d[v]$ only when the current value of $d[v]$ is greater than $d[u] + \text{length}(u,v)$. Whenever we updae $d[v]$, we also save its parent node.

def update (u,v):
   if d[v] > d[u] + length(u,v):
      d[v] = d[u] + length(u,v)
      prev[v] = u               # Remember the previous node

The algorithm maintains the distance of a vertex so that it is always a conservative overestimate; it will only update the a value when a suitable path is discovered to show that the overestimate can be lowered.

The following is the pseudocode for Bellman-Ford:

def bellman_ford(G, s):
   for all v in V:
      d[v] <- infty; pi[s] <- null
   d[s] = 0
   for i in range(n-1):
      for (v, w) in E:
         update(v, w)
   return (d, pi)

Notes:

1. How many times we should update? $n-1$ times
2. What is the order in which we should consider the edges? Any arbitrary order
3. After $k$ rounds of looking at all edges and updating, all shortest paths with $k$ hops would be found and for a vertex $u$ for whom the shortest path is $k$ hops from $s$
4. Since all paths have length at most $n − 1$ (why?) this implies that after $n − 1$ rounds, we would have found the shortest paths for all $u$.

Example: Find the shortest path to all other nodes from node $A$.

We walk through the algorithm in steps as shown below:

(1) Initialize $d[]$ and $\pi[]$:

(2) First iteration: 1 hop from $A$

(3) Second iteration: 2 hops from $A$

(4) Third iteration: 3 hops from $A$

(5) Fourth iteration: 4 hops from $A$

Algorithm terminates!

1. The 4 hops from $A$ are: $A \rightarrow B \rightarrow D \rightarrow E \rightarrow C$, and $A \rightarrow B \rightarrow D \rightarrow C \rightarrow E$. Both of them don’t provide smaller values for $C$ or $E$.
2. So, no more edges to relax. The $d$ array contains the shortest path distance and the $\pi$ array provides the shortest path.

Negative Cycle Detection

What is a negative cycle? A negative-weight cycle is a cycle in a graph whose edges sum to a negative value.

Steps

1. Run Bellman-Ford as above
2. Run the inner loop once more: i.e: for every edge $(u, v) \in E$, call update$(u,v)$
3. If any of the $d[\cdot]$ changes, then the graph has a negative cycle.

Run-time: Run-time is still $O(|V||E|)$.

Claim: If you run Bellman-Ford for $n$ rounds, there will be a change in $d[\cdot]$ iff graph has a negative cycle.

Proof:

1. Assume there is no negative cycle. Therefore the shortest walks from $s$ to $v$ are paths. Paths have length at most $n-1$. So, $n-1$ updates suffice and no updates required on the $n$th round.
2. Assume $\exists$ a negative cycle.
   • After infinitely many rounds of updates, every $d[v] \rightarrow -\infty$
   • So, there must exist a round $> n-1$ with an update
   • But no update in round $i$ implies no further update
   • So every round (including the $n$th) must have an update

Example: Check for negative cycle in the following graph.

The following diagram shows the shortest distances in red after the 4th iteration:

The following diagram shows the shortest distances in red on the 5th iteration:

The 5-hop walk $A \rightarrow C \rightarrow B \rightarrow D \rightarrow C \rightarrow B$ updates $d[B]$ again. Therefore, Bellman-Ford has detected a cycle in this graph!

Back to Graph Algorithms

Data Structures and Algorithms Table of Contents

---

anusha-murali.github.io