Posted by: atri | December 11, 2009

## Lect 39: Bellman-Ford Algorithm (post #1)

(Guest post by Andrew Puleo)

As professor atri gave us at the end of last lecture, we discussed the shortest path algorithm:

$OPT(i, v) = \min\{OPT(i-1, v), \min_{(v,w) \in E} \{c_{v,w} + OPT(i-1, w)\}\}$

• $OPT(i-1,v)$ is the cost of the shortest $v-t$ path that uses  $\le i-1$ edges
• $\min_{(v,w) \in E} \{c_{v,w} + OPT(i-1, w)\}$ is the shortest path that goes through all neighbors

The shortest path algorithm will search for will ultimately give $M[v,i] = OPT(i,v)$

Shortest Path Algorithm:

1. $M[t,0] = 0$ and $v \neq t \in V$, $M[v,0] = \infty$
2. For $i=1,\dots,n-1$
1. For every $v \in V$
• $M[v,i] = \min\{M[v, i-1], \min_{(v,w) \in E} \{c_{v,w} + OPT(i-1, w)\}\}$

$M[s, n-1]$         (cost of shortest path from $s$ to $t$)

Ex:

• $M[s,1]=\min\{M[s,0],\min\{c_{s,t}+M[t,0],c_{s,u}+M[u,0]\}\}$
• $M[u,1] = \min\{\infty, 2+M[t,0]\} = 2$
• $M[t,1] = \min\{0\} = 0$
• $M[t,2] = \min\{0\} = 0$
• $M[u,2] = \min\{M[u,1], 2 + M[t,1]\} = 2$
• $M[s,2] = \min\{M[s,1], \min\{c_{s,u}+ M[u,1], c_{s,t}+ M[t,1]\}\}$

Shortest Path s-t: $M[s,2]$

-3     2

$s$ to $u$ to $latex t$

Runtime Analysis:

1. $O(n)$
2. For $i=1,\dots,n-1$ ($O(n)$)
1. For every $v \in V$($O(n)$)
• $M[v,i] = \min\{M[v, i-1], \min_{(v,w) \in E} \{c_{v,w} + OPT(i-1, w)\}\}$ ($O(n)$)

Which in total is $O(n^3)$. Thus, overall runtime is  $O(n^3)$. We can achieve runtime of $O(mn)$

Longest Path Problem:

Does the longest path have $n-1$ edges? Atri told us this was a trick problem, if you can solve it you’ll get \$1 mill

Although if using a witness (a path $v_1,\dots,v_n$)  we can check if it is the longest path or not.