Posted by: atri | December 11, 2009

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

(Guest post by Chienchung Huang)

Today’s lecture we continue the previous topic ” Shortest Path Problem” the following is the given Algorithm :

• Input: (Directed) Graph $G=(V,E)$ and for every edge $e$ has a cost $c_e$ (can be $<0$) and $t \in V$
• Output: Shortest path from every $s$ to $t$

As we discuss at last lecture the output shortest path will has the negative cost infinity, but the professor mentioned that we not consider negative cycle in this point of time.

Recurrence Relation:

• $OPT(i,v)$ = cost of shortest path from $v$ to $t$ with at most $i$ edges
• $OPT(i,v) = \min \{ OPT(i-1,v), \min_{(v,w) \in E} \{ c_{v,w} + OPT(i-1, w)\} \}$
• $OPT(n-1,v)$ is shortest path cost between $v$ and $t$

There came out from last class.

Q : how to compute the shortest path between $s$ and $t$ ? (Given all $OPT(i,v)$ values.)

Bellman-Ford algorithm :

Compute a matrix $M[0\dots n-1, V ]$ (ultimately $M[v,i]=OPT(I,v)$)

1. $M[t,0] = 0$ and for every $v\neq t\in V$, $M[v,0] = \infty$  (no $0$ edge path from $v$ to $t$)
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}+M[w,i-1]\}\}$.

As we know $M[t,0]$ is $0$
$M[s,1] = \min \{ M[s,0], \min\{c_{s,t} + M[t,0], c_{s,u} + M[u,0]\}\}$

1. I take $M[s,0] = \infty$,
2. look at all neighbor  $u$ and $t$
3. as graph shown on above the and let first look at $s-t$ We got cost of $s-t$ is $1$ and $M[t,0] =0$.
4. Look at second $s-u$ , and we got cost of $s-u$ is $-3$ and $M[u,0] = \infty$
5. add cost of $s-t$ and $M[t,0]$ to get $1$
6. add cost of $s-u$ and $M[u,0]$ to ger $\infty$
7. $M[s,1]=\min\{\infty ,1\}$, so we pick $1$
8. Write the result to matrix , and continue the loop

Run time analysis :

1. $M[t,0] = 0$ and $v\neq t\in, M[v,0] = \infty$  ($O(n)$)
2. For $latex = 1,\dots, n-1$     ($O(n)$)
3. For every $v \in V$      ($O(n)$)

[There are some missing steps, see the book.–Atri]

The running time $O(mn)$.
Longest Path Problem :

• Input: $G=(V,E)$, for every $e\in E$, $c_e=1$ and $s,t\in V$.
• Output: longest path between  $s$ and  $t$