Single source shortest path 7 Problem: Compute shortest path to all vertices from source s estimate dvI estimated shortest path length from s to v predecessor v final edge of shortest path to v induces shortest path treeSingle 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 • predecessor π[v] final edge of shortest path to v • induces shortest path tree