Shortest Path Algorithms

Find the cheapest route through a weighted graph: BFS for equal weights, Dijkstra for non-negative weights, Bellman-Ford when edges can be negative or the number of hops is limited.

Overview

What a shortest path is

A weighted graph gives every edge a number, its weight. A path's weight is the sum of the weights of its edges. The shortest path between two nodes is the path with the smallest total weight, not the one with the fewest edges. Edsger Dijkstra published the best-known algorithm for it in 1959, and Richard Bellman published the one that also handles negative weights in 1958.

Here is the graph that the rest of this topic traces. Every edge points one way.

S, A, C, T — 2 + 3 + 2 — 7
S, B, C, T — 6 + 1 + 2 — 9
S, A, B, C, T — 2 + 4 + 1 + 2 — 9

Problems rarely say the word graph. The problem arrives as flight prices, network delays, a hiking grid with effort scores, or water rising over a map. The first skill is to see the graph. The second is to read the edge weights and pick the algorithm they allow.

Which algorithm

The weights decide the algorithm. V is the number of nodes and E the number of edges.

BFS — all equal — one source to every node — O(V + E) — a queue; the first visit to a node is the shortest
0-1 BFS — only 0 or 1 — one source to every node — O(V + E) — a deque; weight-0 edges go to the front, weight-1 to the back
Dijkstra — non-negative — one source to every node — O((V + E) log V) with a binary heap — a min-heap; the node with the smallest known distance is final
Bellman-Ford — any, as long as no negative cycle is reachable — one source to every node, and it detects negative cycles — O(V × E) — relax every edge, V − 1 rounds
Floyd-Warshall — any, no negative cycle — every pair of nodes — O(V³) — a V × V table, one pass per middle node

Dijkstra step by step

Dijkstra keeps a distance for every node, infinity at first and 0 for the source. It repeats one move: take the unfinished node with the smallest distance, mark it finished, and relax each edge out of it. To relax the edge from u to v with weight w means to check whether dist[u] + w beats dist[v] and, if it does, to store the better value.

The node with the smallest distance can be marked finished because every other unfinished node is at least that far away, and reaching it through them can only add weight. That argument needs weights that are never negative.

A min-heap of (distance, node) pairs finds the smallest distance fast. Python's heapq is a min-heap, so heappop returns the smallest pair; Java's PriorityQueue also returns its least element first, with offer and poll in O(log n). When a node's distance improves, push a new pair rather than searching the heap for the old one. The old pair is now stale: when it comes out, its distance is larger than the stored one, and the loop skips it.

Here is the trace on the example graph. Each row is one pop.

start — 0, ∞, ∞, ∞, ∞ — (0, S)
(0, S) — A = 2, B = 6 — 0, 2, 6, ∞, ∞ — (2, A), (6, B)
(2, A) — B stays 6 (2 + 4 is not better), C = 5 — 0, 2, 6, 5, ∞ — (5, C), (6, B)
(5, C) — T = 7 — 0, 2, 6, 5, 7 — (6, B), (7, T)
(6, B) — C stays 5 (6 + 1 is not better) — 0, 2, 6, 5, 7 — (7, T)
(7, T) — no edges out — 0, 2, 6, 5, 7 — empty

The heap holds at most one entry per relaxation, so at most E entries. Each push and pop costs O(log E), and log E is at most 2 log V, which gives O((V + E) log V). If you only need the distance to one target, stop as soon as that target is popped.

Why negative edges break it

Take a graph with three nodes. S reaches A directly for 2, and B for 5. B reaches A for −4.

(0, S) — A = 2, B = 5 — 2 — 5
(2, A) — A is marked finished — 2 — 5
(5, B) — 5 − 4 = 1 beats 2, but A is already finished — 2 (wrong, should be 1) — 5

The version that skips finished nodes returns 2. A version that lets a node be processed again can find 1 here, but it loses its running-time guarantee, and with a negative cycle it never stops. Adding a constant to every edge does not help either: a route with more edges gets the constant added more times, so the ranking of routes changes. With 4 added to every edge above, S, B, A costs 9 and the direct edge costs 6, so the wrong route now looks cheaper.

Bellman-Ford

Bellman-Ford does not choose an order. It relaxes every edge, then does it again, V − 1 times. After round i, every node whose shortest path uses at most i edges has its final distance. A shortest path never repeats a node, so it has at most V − 1 edges, and V − 1 rounds are enough. If a round changes nothing, stop early.

The trace below uses four nodes, one negative edge, and a deliberately bad edge order to show why more than one round can be needed.

Edges are relaxed in this order in every round: A to T, B to A, S to A, S to B, B to T.

start — 0, ∞, ∞, ∞
1 — A = 4 and B = 2 from S; T = 7 through B. The edge from B to A came before B had a distance. — 0, 4, 2, 7
2 — A = 2 − 3 = −1 through B. The edge from A to T came before A improved. — 0, −1, 2, 7
3 — T = −1 + 3 = 2 through A — 0, −1, 2, 2
4 (check) — nothing changes, so there is no negative cycle — 0, −1, 2, 2

A negative cycle is a loop whose weights add up to less than zero. Going around it again always makes a route cheaper, so no shortest path exists for the nodes it can reach. Bellman-Ford detects it with one extra round: if any edge can still be relaxed after V − 1 rounds, a negative cycle is reachable from the source.

The same algorithm answers at most k stops questions. A route with at most k stops has at most k + 1 edges, so run k + 1 rounds. One detail matters: each round must read the distances from the end of the previous round, so copy the array first. Without the copy, one round can chain several edges together and use more stops than allowed.

Changing the cost or the state

Dijkstra works for any path cost that never gets smaller when the path grows. That covers more than sums.

Network Delay Time — sum of edge times; the answer is the largest distance, or −1 if a node is unreachable — dist[u] + w — smallest
Path with Maximum Probability — product of edge probabilities, each between 0 and 1 — prob[u] × p — largest, so store the negative in a min-heap
Path With Minimum Effort — the largest height difference between neighboring cells on the route — max(effort[u], height difference) — smallest
Swim in Rising Water — the largest cell value on the route, including the start — max(time[u], grid value) — smallest
Cheapest Flights Within K Stops — sum of prices, with a hop limit — one round per hop in Bellman-Ford — not a heap problem

A grid is a graph without an adjacency list. Each cell is a node with up to four neighbors, so a rows × cols grid has rows × cols nodes and about twice that many edges. Dijkstra on a grid runs in O(rows × cols × log(rows × cols)).

When the cost has extra rules, put them in the state. For a hop limit with Dijkstra, the state is (node, stops used) rather than the node alone. A node reached with a higher price but fewer stops is a different state and must not be skipped as finished.

Two other tools show up for grid costs that are a maximum. Binary search on the answer asks, for a threshold t, whether the end is reachable using only steps of size t or less, which is a plain BFS; the smallest t that works is the answer. 0-1 BFS replaces the heap with a deque when every edge weighs 0 or 1: a weight-0 edge puts the neighbor at the front, a weight-1 edge at the back, and the deque stays sorted by distance.

What you will be able to do

Turn a story about prices, delays or terrain into nodes, edges and weights.
Pick BFS, Dijkstra, Bellman-Ford or Floyd-Warshall from the weights and the question, and say why.
Write Dijkstra with a heap and stale-entry skipping, and trace it on a small graph.
Explain why negative edges break Dijkstra and how Bellman-Ford handles them and detects negative cycles.
Adapt the relaxation step for costs that are a maximum or a product, and add hop limits to the state.

When to use it

The cheapest or fastest route between nodes when no edge weight is negative (Dijkstra)
A route limited to k stops, or a graph with negative edge weights (Bellman-Ford)
A grid where moving between cells has a cost, such as effort or time (Dijkstra with cells as nodes)
A route judged by its largest edge or by a product of probabilities (Dijkstra with a changed relaxation)
The shortest route when every edge counts the same (BFS)
Shortest routes between every pair of nodes on a small graph (Floyd-Warshall)

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio