34 Bellman-Ford Algorithm

Dijkstra’s algorithm can fail with negative edge-lengths

Adding a large positive constant to all edge-lengths does not work

Idea: Convert all edge-lengths to be non-negative

• by adding a large positive constant

Adding a large positive constant to all edge-lengths can change identity of shortest paths from $s$

Bellman-Ford Algorithms

Assumptions: There are no negative cycles.
Negative cycles $\Rightarrow$ no shortest paths!

Consequence

For any two vertices $s$ and $t$, there is shortest $s\to t$ path having at most $n-1$ edges, where $n$ is number of vertices

• Let $P$ be a shortest $s\to t$ path with fewest edges
• If a vertex $x$ repeats on $P$, then delete the $x\to x$ cycle from $P$
  • The number of edges on $P$ decreases
  • Length of $P$ cannot increase as there are no negative cycles

For each vertex $v\in V$ and each $0\le i\le n-1$, let

• $\mathrm{OPT}[i,v]$ denote length of shortest $s\to v$ path having at most $i$ edges ($s$ is fixed source)

Setting up the recurrence:

1. If the shortest $s\to v$ path uses at most $i-1$ edges
   • Then the value is $\mathrm{OPT}[i-1,v]$
2. Otherwise the last edge, i.e., the i-th edge has to be $(w,v)$ for some $w\in V$
   • The cost of path is $\mathrm{OPT}[i-1,w]+\mathrm{cost}(w,v)$
   • We need to minimise this over all $w$ such that $(w,v)$ is an edge in $G$

• We need to take minimum over both these choices
  $\mathrm{OPT}[i,v]=\min \{\mathrm{OPT}[i-1,v],{\min }_{w\in V}(\mathrm{length}(w,v)+\mathrm{OPT}[i-1,w])\}$

Algorithm

$$\begin{array}{rl}\text{Algorithm }& \text{Shortest Paths from a vertex }s\text{ to all other vertices in a graph }G=(V,E)\\ 1:& \text{We maintain an }n\times n\text{ table indexed by }0\le i\le (n-1)\text{ and }v\in V\text{ where }\mathrm{OPT}[i,v]\\ & \text{stores the length of shortest }s\to v\text{ path which uses at most }i\text{ edges.}\\ 2:& \text{Define }\mathrm{OPT}[0,s]=0\text{ and }\mathrm{OPT}[0,v]=\infty \text{ for each }v\in V,v\ne s\\ 3:& \text{for }i=1,2,\dots ,n-1\text{ do}\\ 4:& \text{for each }v\in V\text{ do}\\ 5:& \mathrm{OPT}[i,v]=\min \left\{\mathrm{OPT}[i-1,v],\underset{w\in V}{\min }(\mathrm{length}(w,v)+\mathrm{OPT}[i-1,w])\right\}\\ 6:& \text{end for}\\ 7:& \text{end for}\\ & \text{return }\mathrm{OPT}[n-1,v]\text{ for each }v\in V\end{array}$$

Correctness

• Proof by induction on $i$. Base case is $i=0$
• Inductive step is essentially argues the correctness of the recurrence.

Running time

• The table $\mathrm{OPT}$ has $O(n^2)$ entries.
• Computing each entry needs to compute to look up $O(n)$ known entries
  • Computing $\mathrm{OPT}[i,v]$ needs knowledge of $\mathrm{OPT}[i-1,x]$ for all $x\in V$
  • Need to perform $O(n)$ min operations and $O(n)$ additions
• Total running time is $O(n^3)=O(n^2)$ entries $\times (O(n)$ time to compute each entry$)$.