Well-definedness of shortest paths If a graph G contains a negative-weight cycle then some shortest paths may not exist Example: <0 c 2001 by Charles E Leiserson Introduction to Agorithms Day 29 L17.6
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 29 L17.6 Well-definedness of shortest paths If a graph G contains a negative-weight cycle, then some shortest paths may not exist. Example: uu vv … < 0
Single-source shortest paths Problem. From a given source vertex s e v, find the shortest-path weights 8(S, v) for all vE v. If all edge weights w(u, v) are nonnegative, al shortest-path weights must exist IDEA: greedy 1. Maintain a set s of vertices whose shortest path distances from s are known 2. At each step add to s the vertexvEV-s whose distance estimate from s is minimal 3. Update the distance estimates of vertices adjacent to v c 2001 by Charles E Leiserson Introduction to Algorithms Day 29 L17.7
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 29 L17.7 Single-source shortest paths Problem. From a given source vertex s ∈ V, find the shortest-path weights δ(s, v) for all v ∈ V. If all edge weights w(u, v) are nonnegative, all shortest-path weights must exist. IDEA: Greedy. 1. Maintain a set S of vertices whose shortestpath distances from s are known. 2. At each step add to S the vertex v ∈ V – S whose distance estimate from s is minimal. 3. Update the distance estimates of vertices adjacent to v
Diikstra's algorithm d]∈-0 for each y∈-{s} do dvI S< Q← Q is a priority queue maintaining V-S while≠⑧ do← EXTRACT-MIN(Q S←SU{ for each y∈Ao/ do if dv> du+w(u, v) relaxation then dlv]<d[u]+w(u, v) step Implicit dECrEase-Key c 2001 by Charles E Leiserson Introduction to Agorithms Day 29 L17. 8
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 29 L17.8 Dijkstra’s algorithm d[s] ← 0 for each v ∈ V – {s} do d[v] ← ∞ S ← ∅ Q ← V ⊳ Q is a priority queue maintaining V – S while Q ≠ ∅ do u ← EXTRACT-MIN(Q) S ← S ∪ {u} for each v ∈ Adj[u] do if d[v] > d[u] + w(u, v) then d[v] ← d[u] + w(u, v) relaxation step Implicit DECREASE-KEY
Example of Dijkstra’s algorithm Graph with B D nonnegative 10 edge weights: E c 2001 by Charles E Leiserson Introduction to Agorithms Day29L17.9
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 29 L17.9 Example of Dijkstra’s algorithm AA BB DD CC EE 10 3 14 79 8 2 2 Graph with nonnegative edge weights:
Example of Dijkstra’s algorithm Initialize B D 10 0(A Q: A B C D E E S:{} c 2001 by Charles E Leiserson Introduction to Agorithms Day29L17.10
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 29 L17.10 Example of Dijkstra’s algorithm AA BB DD CC EE 10 3 14 79 8 2 2 Initialize: Q: ABCDE 0 ∞∞∞∞ S: {} 0 ∞ ∞ ∞ ∞