Shortest Path Algorithms

Finding the shortest path between vertices is one of the most widely applied problems in computer science. GPS navigation, network routing, package dependency resolution, and game AI all depend on shortest path algorithms as a fundamental building block. Understanding how these algorithms work — and when each one applies — is essential for reading, writing, and reviewing graph-related code.

The Problem#

Given a weighted graph, find the path from a source vertex to a destination — or to all other vertices — that minimizes the total edge weight. In unweighted graphs, this reduces to finding the path with the fewest edges.

Algorithm Overview#

Different algorithms are suited to different graph types. Choosing the wrong one can produce incorrect results or perform far worse than necessary.

BFS for Unweighted Graphs#

When all edges have equal weight — that is, the graph is unweighted, or all weights are treated as 1 — BFS guarantees the shortest path. BFS explores vertices in layers: level 0 is the source, level 1 contains its immediate neighbors, level 2 contains their neighbors, and so on. Because BFS processes closer vertices first, the first time it reaches a vertex it must be via the fewest edges possible. No shorter-hop route can exist, because all shorter routes would already have been explored in earlier layers.

Dijkstra's Algorithm#

Dijkstra's algorithm computes shortest paths from a source vertex to all others in graphs with non-negative edge weights. The approach is greedy: at each step, select the unvisited vertex with the smallest known distance and relax its outgoing edges — that is, check whether traveling through this vertex offers a shorter route to each of its neighbors, and update the neighbor's distance if so. Once a vertex is selected, its distance is considered final and is never revised downward.

The correctness of this greedy strategy rests on a key insight: with non-negative edge weights, once you select the vertex with the smallest tentative distance, no undiscovered path can possibly improve on it. Any alternative route must travel through other edges, each of which adds a non-negative cost — so the current best distance is already optimal. This guarantee breaks down the moment a negative edge is introduced.

Step-by-Step Example#

The following trace runs Dijkstra on the graph from the introduction (A→B: 4, A→C: 2, C→B: 1, B→D: 3, C→D: 5). At each step, we pop the vertex with the smallest distance and update its neighbors.

Notice how C's path improved B's distance from 4 to 3 in Step 2. The entry (4, B) remains in the priority queue but is skipped when popped — because by then, dist[B] has already been updated to 3. This "lazy deletion" pattern (skipping stale entries via the if d > dist[u]: continue check) is how the implementation stays efficient without modifying entries already in the queue.

Why Dijkstra Fails with Negative Weights#

Dijkstra's greedy correctness relies on one assumption: with non-negative edge weights, once a vertex is selected as having the smallest tentative distance, that distance cannot be improved by any path discovered later. Adding non-negative edges to a route only makes it longer, so the current minimum is already optimal.

A single negative edge breaks this assumption. Consider a graph where there are two ways to reach vertex B: a direct edge with cost 1, and a detour through C with total cost 2 + (−5) = −3. Dijkstra greedily selects and finalizes B at cost 1 — the smallest known distance at that moment. When C is processed later and the negative edge C → B is discovered, B's distance should be updated to −3, but it has already been marked as final and will not be reconsidered. The result is a wrong shortest-distance value for B.

The diagrams below illustrate this failure conceptually:

The diagram above shows the conceptual failure mode: when a vertex is processed too early (before all shorter paths through negative edges are considered), its distance becomes permanently wrong. In practice, graphs with negative edge weights require Bellman-Ford, which does not make this early-finalization assumption.

Bellman-Ford Algorithm#

Bellman-Ford handles graphs with negative edge weights and can detect negative cycles — cycles where the total edge weight is negative. A negative cycle makes shortest paths undefined for any vertex reachable from it, because you could keep looping around the cycle to reduce the distance indefinitely.

Unlike Dijkstra's greedy approach, Bellman-Ford uses repeated relaxation: it iterates over every edge in the graph V−1 times, progressively tightening distance estimates from the source.

Why V−1 iterations? In a graph with V vertices, any shortest path that contains no cycles visits at most V−1 edges. Each full pass through all edges guarantees that the shortest path to at least one more vertex is correctly computed. After V−1 passes, all reachable vertices have their true shortest distances — unless a negative cycle exists. A final extra pass is then used as a detection step: if any distance can still be reduced, a negative cycle must be reachable.

Floyd-Warshall Algorithm#

Floyd-Warshall computes shortest paths between all pairs of vertices using dynamic programming. The core idea is to consider every vertex as a potential intermediate stop on the way from i to j. For each vertex k (iterated from 0 to V−1), the algorithm asks: for every pair (i, j), is the path from i to j shorter if it passes through k? If so, the distance is updated.

The order of the outer loop is critical. When k is the current intermediate vertex, all distances using only vertices 0 through k−1 as intermediates have already been computed in previous iterations. This means dist[i][k] and dist[k][j] are already optimal for paths restricted to those earlier intermediates, making the update dist[i][j] = dist[i][k] + dist[k][j] correct and safe. By the time k reaches V−1, every possible intermediate has been considered for every pair, yielding all-pairs shortest paths.

Algorithm Comparison#

Decision Flowchart#

Use this flowchart to quickly select the right algorithm. Default to the simpler, faster option and only move to a more powerful algorithm when the graph's properties require it.

Reviewing AI-Generated Code#

Knowing the constraints and failure modes of each algorithm equips you to critically evaluate AI-generated code. AI tools often default to the most familiar algorithm — commonly Dijkstra — regardless of whether the graph has negative weights or whether an all-pairs solution is needed. Develop the habit of checking these key points:

What to Verify#

Common AI Pitfalls#

Questions to Ask AI#

When AI generates shortest path code, probe it with targeted questions:

• Does this algorithm handle negative edge weights correctly?
• What happens when no path exists to the destination?
• How would you reconstruct the actual path, not just the distance?
• What is the time complexity, and does it match the chosen algorithm?

Summary#

Algorithm selection hinges on three questions: Is the graph weighted? Are negative weights possible? Do you need distances from a single source or between all pairs? Default to BFS for unweighted graphs and Dijkstra for weighted ones — they are faster and simpler. Reach for Bellman-Ford when negative weights are unavoidable, and Floyd-Warshall when you need all-pairs distances and the graph is small or dense enough that its O(V³) cost is acceptable. Use the decision flowchart above as a quick reference.