- Single Source, Multiple Targets:
- Can represent shortest path from start to every vertex as a shortest paths tree with V-1 edges.
- Can find the SPT using Dijkstra’s algorithm.
- Single Source, Single Target:
- Dijkstra’s is inefficient (searches useless parts of the Graph).
- Can represent shortest path as path (with up to V-1 vertices, but probably far fewer).
- A* is potentially much faster than Dijkstra’s.
- Consistent heuristic guarantees correct solution.