Bellman Ford algorithm Finds the shortest paths, from a given source node, say node 1, to all other nodes General idea: First find the shortest single arc path, Then the shortest path of at most two arcs, etc Let dij=o if (i,j)is not an arc Let Di()be the shortest distance from 1 to i using at most h arcs D()=d1i;萨1D1(1)=0 Di(h+1)=min 0 [Dj(h)+ dj];i1 D1(h +1)=0 If all weights are positive, algorithm terminates in N-1 steps.Bellman Ford algorithm • Finds the shortest paths, from a given source node, say node 1, to all other nodes. • General idea: – First find the shortest single arc path, – Then the shortest path of at most two arcs, etc. – Let dij= ∞ if (i,j) is not an arc. • Let Di(h) be the shortest distance fro m 1 to i using at most h arcs. – Di(1) = d1i ; i≠1 D1(1) = 0 – Di(h+1) = min {j} [Dj(h) + dji] ;i ≠1 D1(h +1) = 0 • If all weights are positive, algorithm terminates in N-1 steps. Eytan Modiano Slide 6