Introduction to algorithms 6.046J/18,401J/SMA5503 Lecture 17 Prof erik demaine
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 17 Prof. Erik Demaine
Paths in graphs Consider a digraph g=(v, E)with edge-weight function w:E→>R. The weight of path p=v1→ →>…→> vi is defined to be (D)=∑(n,1) Example: c 2001 by Charles E Leiserson Introduction to Agorithms Day 29 L17.2
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 29 L17.2 Paths in graphs Consider a digraph G = (V, E) with edge-weight function w : E → R. The weight of path p = v1 → v2 → L → vk is defined to be ∑ − = = + 1 1 1 ( ) ( , ) k i i i w p w v v . v1 v1 v2 v2 v3 v3 v4 v4 v5 v5 4 –2 –5 1 Example: w(p) = –2
Shortest paths a shortest path from u to v is a path of minimum weight from u to v. The shortest- path weight from u to v is defined as S(u, v)=min((p): p is a path from u to v) Note: 8(u, v)=00 if no path from u to v exists c 2001 by Charles E Leiserson Introduction to Agorithms Day29L17.3
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 29 L17.3 Shortest paths A shortest path from u to v is a path of minimum weight from u to v. The shortestpath weight from u to v is defined as δ(u, v) = min{w(p) : p is a path from u to v}. Note: δ(u, v) = ∞ if no path from u to v exists
Optimal substructure Theorem. A subpath of a shortest path is a shortest path roof. Cut and paste c 2001 by Charles E Leiserson Introduction to Agorithms Day 29 L17.4
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 29 L17.4 Optimal substructure Theorem. A subpath of a shortest path is a shortest path. Proof. Cut and paste:
Triangle inequality Theorem. For alluvx e v we have 6(,)≤8(2x)+6(x,y) 7o0 ux x X c 2001 by Charles E Leiserson Introduction to Agorithms Day29L17.5
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 29 L17.5 Triangle inequality Theorem. For all u, v, x ∈ V, we have δ(u, v) ≤ δ(u, x) + δ(x, v). uu Proof. xx vv δ(u, v) δ(u, x) δ(x, v)
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 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 ∞ ∞ ∞ ∞