[prev] 59 [next]

Edge Relaxation

Assume: dist[] and pred[] as above   (but containing data for shortest paths discovered so far)

dist[v] is length of shortest known path from s to v
dist[w] is length of shortest known path from s to w

Relaxation updates data for w if we find a shorter path from s to w:

[Diagram:Pic/relaxation.png]

Relaxation along edge e=(v,w,weight):

  • if  dist[v]+weight < dist[w]  then
       update dist[w]:=dist[v]+weight  and  pred[w]:=v