《算法入门》（英文版）Lecture 17 Prof. Erik Demaine

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 shortest￾path 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)