Single source shortest path Problem: Compute shortest path to all vertices from source s estimate dvI estimated shortest path length from s to vSingle Source Shortest Path 8 9 u v 1 5 7 x y 2 0 10 5 7 9 2 3 4 6 s Problem: Compute shortest path to all vertices from source s • estimate d[v] estimated shortest path length from s to v