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:
Relaxation along edge e=(v,w,weight) :
- if
dist[v]+weight < dist[w] then
update dist[w]:=dist[v]+weight and pred[w]:=v
|