Pattern GuideShortest Path Algorithms

Shortest Path Algorithms

"Navigating weighted graphs: relax every edge, trust the cheapest known route."

11 min read Advanced Dijkstra: O((V+E) log V)
01
CORE INTUITION

'Shortest' Means 'Cheapest', Not 'Fewest Hops'

📍

Plain BFS finds the path with the fewest edges — perfect when every step costs the same. The moment edges carry different weights (time, money, effort), the path with the fewest hops is no longer guaranteed to be the cheapest one. A 1-hop route that costs 50 can lose to a 3-hop route that costs 12.

Relaxation is the one operation this whole family is built on: for an edge (u → v) with weight w, check whether going through u gives a cheaper way to reach v than whatever we currently believe is v's best distance — if dist[u] + w < dist[v]: dist[v] = dist[u] + w. Every algorithm below is just a different strategy for deciding which order to relax edges in.

A priority queue (min-heap) is what lets Dijkstra always relax the cheapest known frontier node next, instead of processing nodes in arbitrary or arrival order.

02
VISUALIZER

Interactive Weighted Grid (Dijkstra)

Every open cell shows its cost (1-9) to enter. Click cells to toggle walls. Watch the priority queue always pop the cheapest known frontier cell next — not just the nearest one by hop count.

S
3
1
1
1
2
2
🧱
🧱
4
🧱
1
1
5
1
2
🧱
3
🧱
🧱
1
🧱
6
1
3
1
8
1
🧱
2
1
2
1
9
1
T

Simulation Status

Click Play or step forward to start.

PRIORITY QUEUE (cheapest first)Size: 1
(0,0)@0
Delay:500ms
03
DECISION TABLE

Which Algorithm, and When

How to choose: unweighted graph → BFS. Non-negative weights → Dijkstra. Negative edges allowed → Bellman-Ford. Need every pair's shortest path → Floyd-Warshall. Graph is a DAG → topological order + relax (fastest of all).

AlgorithmUse WhenTimeSpaceWhy
BFSUnweighted (all edges cost 1)O(V + E)O(V)First visit is always the shortest, by construction.
DijkstraNon-negative weightsO((V+E) log V)O(V + E)Greedily finalizing the cheapest frontier node is provably safe — as long as nothing can ever get cheaper later.
Bellman-FordNegative edges (and cycle detection)O(V · E)O(V)Relaxes every edge, order-independent, V-1 times — enough passes for the truth to fully propagate.
Floyd-WarshallAll-pairs shortest pathsO(V³)O(V²)DP over "allowed intermediate nodes" — simple triple loop, no queue needed.
Topological + RelaxDAG (no cycles)O(V + E)O(V)Process nodes in dependency order — one relax pass per edge is enough, no heap needed.
04
BLUEPRINTS

Golden Templates

1. BFS Distance (Unweighted)

bfsDistance.js
1
function bfsDistance(grid, start, target) {
2
const queue = [[start, 0]];
3
const visited = new Set([start]);
4
5
while (queue.length > 0) {
6
const [node, dist] = queue.shift();
7
if (node === target) return dist; // first hit = shortest (unweighted!)
8
9
for (const neighbor of getNeighbors(grid, node)) {
10
if (!visited.has(neighbor)) {
11
visited.add(neighbor);
12
queue.push([neighbor, dist + 1]);
13
}
14
}
15
}
16
return -1; // unreachable
17
}

2. Dijkstra (Priority Queue)

dijkstra.js
1
function dijkstra(graph, start) {
2
const dist = new Map([[start, 0]]);
3
const pq = [[start, 0]]; // [node, distance] — use a real heap in production
4
5
while (pq.length > 0) {
6
pq.sort((a, b) => a[1] - b[1]);
7
const [u, d] = pq.shift();
8
if (d > (dist.get(u) ?? Infinity)) continue; // stale entry, skip
9
10
for (const [v, w] of graph.get(u) || []) {
11
const nd = d + w;
12
if (nd < (dist.get(v) ?? Infinity)) {
13
dist.set(v, nd);
14
pq.push([v, nd]);
15
}
16
}
17
}
18
return dist;
19
}

3. Bellman-Ford (Negative Edges OK)

bellmanFord.js
1
// Shown in JS only — every language relaxes the same way: loop over
2
// ALL edges, V-1 times. No graph traversal order matters here.
3
function bellmanFord(edges, V, start) {
4
const dist = new Array(V).fill(Infinity);
5
dist[start] = 0;
6
7
for (let i = 0; i < V - 1; i++) {
8
for (const [u, v, w] of edges) {
9
if (dist[u] + w < dist[v]) {
10
dist[v] = dist[u] + w;
11
}
12
}
13
}
14
15
// Vth pass: if anything still improves, there's a negative cycle
16
for (const [u, v, w] of edges) {
17
if (dist[u] + w < dist[v]) {
18
throw new Error('Negative cycle detected');
19
}
20
}
21
return dist;
22
}
05
RECOGNITION

How to Spot This Pattern

🔎 "Minimum cost / time / effort" to get from A to B.

🔎 "Cheapest flights within K stops", "network delay time".

🔎 "Path with minimum effort" or "path with maximum probability".

🔎 Edge weights are explicitly NOT all equal — plain BFS would give the wrong answer.

Named problems: Network Delay Time · Cheapest Flights Within K Stops · Path With Minimum Effort · Swim in Rising Water

06
PITFALLS

Common Mistakes

Dijkstra with Negative Edges

Dijkstra assumes a finalized node's distance can never improve later. A negative edge breaks that assumption and produces a wrong answer silently — no error, just an incorrect result.

Forgetting to Skip Stale PQ Entries

A node can be pushed onto the priority queue multiple times with different distances before it's finalized. Always check if (d > dist[u]) continue; after popping — the demo above flashes exactly this moment.

BFS on a Weighted Graph

BFS finds the path with the fewest edges, not the cheapest one. The moment weights differ, a plain queue gives the wrong "shortest" path.

O(V²) Matrix on a Sparse Graph

Scanning a full V×V adjacency matrix to find the next cheapest node works, but wastes time on graphs where E is much smaller than V². An adjacency list + priority queue is the faster default.

07
PRACTICE

Ready to Practice?

Dijkstra's AlgorithmMedium
Network Delay TimeMedium
Bellman-Ford AlgorithmMedium
Shortest Path in Binary MatrixMedium

"Explore the cheapest, trust the order, and never look back once the distance is locked."