Shortest Path
Cheapest route through a weighted graph, where the algorithms differ mainly in what they are allowed to assume about the weights.
Every algorithm here is built from one operation. Relaxation says: if dist[u] plus the weight of u to v is less than dist[v], write the smaller number into dist[v] and record u as the predecessor of v. Run enough relaxations in a safe order and every distance is final; the predecessor array is what you walk backwards to get the route itself.
The order is the algorithm. Dijkstra assumes no weight is negative, and that lets it settle vertices in increasing distance order with a priority queue, each vertex finished once, O((V + E) log V). Bellman-Ford assumes nothing and pays V - 1 rounds of relaxing every edge, O(V * E), with one extra round used as a negative-cycle detector. Floyd-Warshall answers all pairs at once in O(V^3) by admitting one more vertex as a stopover each round.
The shape of the graph can beat all three. In a DAG, a topological order is already a safe relaxation order, so one pass is enough and negative weights are fine. When every weight is 0 or 1, a deque replaces the heap: a zero edge goes on the front, a one edge on the back. And when you have a lower bound on the distance still to travel, A* orders the queue by g + h and expands a fraction of what Dijkstra would, while still returning the optimum as long as that bound never overestimates.
After this you can
- Relax an edge and rebuild the route from the predecessor array
- Choose between Dijkstra, Bellman-Ford, Floyd-Warshall and a single DAG pass from the weights and the number of sources
- Explain why one negative edge breaks the argument that a settled vertex is final
- Detect a negative cycle and say what a shortest path means once one exists
- State the condition a heuristic has to satisfy before A* is still optimal
Unsettled vertices with a known distance: 0 at 0. The smallest is 0, so settle it: 0 is final, because every other route into 0 would pass through something at least as far and edges never shorten a path.
In this order
- DijkstraRepeatedly settle the unsettled vertex with the smallest tentative distance and relax its edges.
- 0-1 BFSA deque replaces the heap when weights are 0 or 1: a 0 edge pushes to the front, a 1 edge to the back.
- Bellman-FordRelax every edge V-1 times; a further improvement means a negative cycle.
- DAG Shortest PathRelax each vertex's edges once, in topological order: one pass, negative weights allowed.
- Floyd-WarshallAdmit one stopover vertex per round and relax every pair through it; the matrix converges in n rounds.
- A* SearchBest-first search ordered by g + h, distance so far plus an admissible estimate of what is left; optimal and far more focused than BFS.
Where people go wrong
Negative weights and Dijkstra
Dijkstra settles a vertex the moment it leaves the heap, on the argument that every remaining edge can only add to the distance. One negative edge destroys that argument, and the result is a wrong distance returned quietly with no error anywhere. Use Bellman-Ford, or a topological pass if the graph is acyclic.
Stale entries left in the priority queue
Most implementations push a new (distance, vertex) pair instead of decreasing a key, so the heap holds outdated copies of vertices. When you pop one whose stored distance is worse than dist[v], skip it, or you relax the same vertex twice from an old value.
A negative cycle has no shortest path
The V-th Bellman-Ford pass tells you a negative cycle exists, not which vertices it can reach. Any vertex reachable from the cycle has no finite distance, so mark those rather than printing whatever number happens to be in the array.
Or a different category
Graph Traversal
Every edge costs the same, so BFS already gives the fewest-edge path in O(V + E) with no heap at all.
Minimum Spanning Tree
You want the cheapest set of edges that keeps everything connected; the route between two vertices inside that tree is usually not the shortest path.