Single Source Shortest Path

Synopsis

A single source shortest path algorithm discovers the shortest paths between a single node and all the other nodes. There are three algorithms that can do this, depending on the situation.

• Unweighted graphs use BFS
• Weighted graphs with no negative edges use Dijkstra’s algorithm
• Weighted graphs with negative edges use the Bellman Ford algorithm.

Videos

• BFS for Shortest Path
• Dijkstra’s Algorithm
• Bellman-Ford and SPFA

Recommended Reading

• Competitive Programming 4, section 4.4

Problems

• 429 - Word Transformation