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