Single Destination Shortest path 8 10 08 y x Problem: Compute shortest path from all vertices to goal g estimate hv estimated shortest path length from s to v descendant bv first edge of shortest path from v to g induces shortest path tree9 8 v u 1 7 5 y x 2 0 10 5 7 9 6 4 3 2 g Single Destination Shortest Path Problem: Compute shortest path from all vertices to goal g • estimate h[v] estimated shortest path length from s to v • descendant b[v] first edge of shortest path from v to g • induces shortest path tree