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