Shortest Path Algorithms: Complete Comparison

The Shortest Path Problem

Finding the shortest path between vertices in a graph is one of the most fundamental problems in computer science. But there is no single "best" algorithm — the right choice depends on your graph's properties: Is it weighted? Are weights negative? Do you need single-source or all-pairs? Is it sparse or dense?

Algorithm Comparison Table

Decision Flowchart

BFS: The Simplest Case

When: Unweighted graph (or all edges have same weight) Why: BFS explores in order of distance from source — first it finds all vertices at distance 1, then 2, etc. Key idea: Queue-based level-by-level expansion

Dijkstra: The Workhorse

When: Weighted graph with non-negative edges, single source Why: Greedy approach — always process the closest unvisited vertex Key idea: Priority queue (min-heap) ensures we process vertices in distance order

The "relaxation" step: if dist[u] + weight(u,v) < dist[v], update dist[v].

Once a vertex is popped from the heap, its distance is final (greedy guarantee from non-negative weights).

Bellman-Ford: Handling Negative Weights

When: Graph may have negative edges (but ideally no negative cycles) Why: Relaxes ALL edges V-1 times, guaranteed to find shortest paths Key idea: On iteration i, all shortest paths using ≤ i edges are correct

Also detects negative cycles: if any edge can still be relaxed after V-1 iterations, a negative cycle exists.

Floyd-Warshall: All Pairs

When: Need shortest path between every pair of vertices, V is small (≤400) Why: Elegant DP approach — try each vertex as intermediate Key idea: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for each k

Three nested loops. Simple to code, but O(V³) limits it to small graphs.

A*: Informed Search

When: Single source to single target, and you have a heuristic function Why: Uses a heuristic h(v) to estimate remaining distance, focusing search toward the target Key idea: Priority = actual distance g(v) + estimated remaining h(v)

The heuristic must be admissible (never overestimate) for A* to find optimal paths.

0-1 BFS: Special Case Optimization

When: All edge weights are either 0 or 1 Why: Use a deque — push weight-0 edges to front, weight-1 to back Advantage: O(V+E) instead of O((V+E) log V) for Dijkstra

Practical Recommendations

1. Default choice: Dijkstra with binary heap. It handles 99% of shortest path problems you will encounter.
2. Negative weights: Bellman-Ford. Slow but correct.
3. Small dense graphs, all pairs: Floyd-Warshall. Simple to code.
4. Unweighted: Always BFS. Simpler and faster than Dijkstra.
5. Game pathfinding: A* with Manhattan distance (grid) or Euclidean distance heuristic.
6. Competitive programming: Know all five. The constraints tell you which to use.