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
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: