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.

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: