Shortest Path Algorithm Comparison: Two Questions Decide

Which shortest path algorithm should you use? BFS, Dijkstra's, Bellman-Ford, and Floyd-Warshall are built for different graph types, and most resources explain them individually without ever telling you when each one applies. This shortest path algorithm comparison reduces the choice to two questions about your graph. The answers point to exactly one algorithm every time.

The shortest path algorithm comparison framework

Shortest path algorithms fall into four categories based on two graph properties: whether edges have weights, and whether those weights can be negative. Unweighted graphs use BFS. Non negative weighted graphs use Dijkstra's algorithm. Graphs with negative weights use Bellman-Ford. All pairs queries use Floyd-Warshall. That's the entire decision matrix.

The first question eliminates BFS or enables it. The second separates Dijkstra from Bellman-Ford. And if you need shortest paths between every pair of nodes rather than from a single source, Floyd-Warshall is the right choice.

BFS as a shortest path algorithm

BFS finds shortest paths in unweighted graphs because it explores nodes layer by layer. All nodes at distance 1 get processed before distance 2, all at distance 2 before distance 3. The first time BFS reaches a node, it's found the shortest path to that node. There's no cheaper route hiding behind a longer queue entry.

Why does BFS break on weighted graphs? If edge A to B weighs 1 and edge A to C weighs 5, BFS treats both as "one step." It might process C before discovering a cheaper two edge path through B. The layer by layer guarantee assumes equal weight per edge. When that assumption fails, the guarantee goes with it.

In interviews, BFS shortest path problems show up as grid traversals with uniform step weight, word transformation chains where each transformation counts as one step, and minimum step puzzles. The trigger is always the same: every move has the same weight. If you spot that constraint in the problem statement, BFS is your algorithm.

For a walkthrough of BFS mechanics and how it contrasts with DFS in traversal strategy, see our BFS vs DFS comparison.

Dijkstra's algorithm for non negative weighted graphs

When edges have different weights but none are negative, Dijkstra's algorithm is the standard choice. It maintains a priority queue of nodes sorted by current shortest known distance from the source. At each step, it extracts the node with the smallest distance and relaxes its outgoing neighbors, checking whether a shorter path exists through the current node.

The proof is one observation. If every weight is zero or greater, any path through additional edges can only increase the total distance. The node with the smallest known distance can't be reached more cheaply through some longer detour. That property, known as optimal substructure, is what makes the greedy approach valid.

Tracing Dijkstra on a 5-node graph

Consider finding the shortest distance from node A to node E in this graph.

`
A → B (4), A → C (2)
C → B (1), C → D (5)
B → D (3), D → E (1)
`

Notice that B's distance dropped from 4 to 3 when we processed C. That's relaxation at work. But once B was extracted at distance 3, that value was final. No later step changed it.

Now imagine edge C to B had weight -3 instead of 1. After processing C, B's distance would become 2 + (-3) = -1. But we might've already finalized nodes based on the assumption that distances only grow. A negative edge can create shorter paths to nodes we already locked in, and that breaks the invariant entirely. This isn't some rare edge case. It's a hard constraint of the algorithm, and it's exactly when you reach for Bellman-Ford.

Codeintuition's understanding lesson for Dijkstra traces this invariant step by step, showing the priority queue state at every extraction. The identification lesson then covers the structural triggers that separate Dijkstra problems from BFS problems in interviews.

Bellman-Ford for graphs with negative weights

Bellman-Ford takes a fundamentally different approach. Instead of greedily finalizing nodes one at a time, it relaxes every edge in the graph V-1 times, where V is the vertex count.

Why V-1 passes? The longest possible shortest path in a graph with V nodes has at most V-1 edges. Each pass guarantees that shortest paths using K edges are correctly computed after K passes. After V-1 passes, all shortest distances are final regardless of edge processing order. The tradeoff is speed: Bellman-Ford runs in O(V · E), which is slower than Dijkstra's O((V + E) log V) for sparse graphs. You wouldn't choose it when Dijkstra works. But when negative weights exist, Bellman-Ford gives correct results where Dijkstra doesn't.

In interviews, Bellman-Ford appears in currency exchange problems where negative log weights enable arbitrage detection, network optimization with weight penalties, and anywhere constraints explicitly mention negative weights. That constraint mention is your signal. If the problem says "weights can be negative," you've identified the algorithm before reading the rest of the problem. The negative cycle detection bonus is what makes Bellman-Ford show up in questions about arbitrage opportunities or infinite discount loops, two problem types where Dijkstra would silently produce wrong answers.

Floyd-Warshall for all pairs shortest paths

The three algorithms above solve the single source shortest path problem: distances from one starting node to all others. Floyd-Warshall solves something different. It computes shortest distances between every pair of nodes simultaneously.

It's a dynamic programming algorithm with a clean recurrence. For each pair of nodes (i, j), it checks whether routing through an intermediate node k produces a shorter path by comparing dist[i][j] against dist[i][k] + dist[k][j]. After considering all V possible intermediate nodes, the complete shortest distance matrix is done.

The Floyd-Warshall implementation is three nested loops.

The complexity is O(V³), which sounds steep. But consider the alternative: running Dijkstra from every node gives O(V · (V + E) log V). Dense graphs where E approaches V² push that to O(V³ log V), and Floyd-Warshall actually wins.

Sparse graphs with non negative weights do better with V runs of Dijkstra. Dense graphs or graphs with negative weights (but no negative cycles) favor Floyd-Warshall. The crossover depends on graph density, and most interview problems won't ask for all pairs computation. But when one does, you'll recognize it. Problems asking you to "find the shortest distance between every pair of cities" or "determine the minimum travel distance between all nodes" are Floyd-Warshall signals.

Comparison applied to interviews

The practical decision process for any shortest path problem:

Where people get tripped up is separating #2 from #3. Most weighted graph problems in interviews use non negative weights, so Dijkstra is the default. But problems mentioning penalties, decreasing values, or exchange rates are hinting at negative weights. Read the constraints before you pick your algorithm.

The broader skill here, reading problem constraints to pick the right algorithm class, is what separates pattern recognition from memorization. Codeintuition's graph course teaches each shortest path algorithm from its invariant rather than its implementation. You don't just learn Dijkstra's code. You learn why the greedy invariant holds, which constraints break it, and how to identify which algorithm a new problem needs before writing a single line.

Six weeks from now, you open a coding assessment. The problem describes a weighted directed graph with non negative edge weights and asks for the shortest route between two nodes. Instead of scrolling through four mental flashcards, you've already asked the two questions, confirmed the constraints, and started building the priority queue. The algorithm choice took five seconds because you understood the invariant, not the implementation.

Start with the two questions. The right algorithm follows.