Breadth-first search finds the shortest path by treating every edge as costing exactly one step — which only works because in an unweighted graph that's true. Give edges different costs (a road network where blocks vary in length, or terrain that's slow to cross) and BFS's guarantee breaks: the first-discovered path is the path with the fewest edges, not the path with the lowest total cost. Dijkstra's algorithm fixes this by replacing BFS's plain queue with a priority queue ordered by accumulated distance instead of by discovery order — always processing whichever known cell is currently cheapest to reach, not whichever was discovered first.
Every cell here costs something to enter — click a cell to cycle its cost through 1 → 3 → 9 (green is the start, orange is the end — fixed, always cost 1). The default terrain has a costly marsh band across the middle. Step through the search and watch the priority queue below the grid: it's shown sorted cheapest-first, the current cell being popped gets a bold border, cells it discovers (or finds a cheaper route to) get pushed and shaded, and once the end is popped the cheapest path lights up — total cost included. Notice it's usually not a straight line through the marsh; it routes around, even though a hop-counting search like BFS would have no reason to prefer one route over the other.
The priority queue is the whole mechanism, and the key invariant is: whenever a cell is popped, its current known distance is already the shortest possible distance to it. That holds because the queue always hands back the globally cheapest unfinished cell, and every edge cost is non-negative — so there's no way a path through some more-expensive-so-far cell could ever undercut the cheapest one. This is exactly BFS's "first visit is shortest" argument, generalized: BFS gets away with a plain FIFO queue because when every edge costs 1, "discovered earliest" and "cheapest so far" are the same ordering. Once edges have different costs those two orderings diverge, and only the priority queue tracks the one that still gives a correctness guarantee.
One consequence worth noticing in the demo: a cell can be pushed onto the queue more than once. If a cheaper route to an already-queued cell is found later, the new (lower) distance is pushed as a fresh entry rather than trying to modify the old one in place — plain array-backed priority queues don't support an efficient "decrease this key" operation. The stale, higher-distance entry is left sitting in the queue and simply gets popped and skipped later, since by then the cell's already finalized with a better distance. It's wasted queue space, not a correctness problem: the distance check on relaxation still stops a stale entry from being used.
Grid version, tracking a parent pointer per cell exactly like BFS, but relaxing distances through a numeric cost grid instead of just marking cells visited:
function dijkstra(grid, rows, cols, start, end) {
const key = (r, c) => r * cols + c;
const n = rows * cols;
const dist = new Array(n).fill(Infinity);
const visited = new Array(n).fill(false);
const parent = new Array(n).fill(-1);
const startK = key(...start), endK = key(...end);
dist[startK] = 0;
// Array-backed priority queue: [distance, cellKey] pairs, extract-min by
// linear scan. See Complexity below for why production code swaps this
// for a binary heap instead.
const pq = [[0, startK]];
while (pq.length) {
let mi = 0;
for (let i = 1; i < pq.length; i++) if (pq[i][0] < pq[mi][0]) mi = i;
const [d, cur] = pq.splice(mi, 1)[0];
if (visited[cur]) continue; // stale entry, already finalized cheaper
visited[cur] = true;
if (cur === endK) break;
const r = Math.floor(cur / cols), c = cur % cols;
for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
const nk = nr * cols + nc;
if (visited[nk]) continue;
const nd = d + grid[nk]; // grid[nk] is the cost to enter that cell
if (nd < dist[nk]) {
dist[nk] = nd;
parent[nk] = cur;
pq.push([nd, nk]);
}
}
}
if (!visited[endK]) return null; // unreachable
const path = [];
for (let cur = endK; cur !== -1; cur = parent[cur]) path.push(cur);
return { path: path.reverse(), cost: dist[endK] };
}Negative edge weights break it. The correctness argument above leans entirely
on "no path through a not-yet-finalized cell can be cheaper," which is only true if every edge
cost is non-negative. A single negative edge can make a path that looks more expensive so far
actually cheaper once you follow it further — Dijkstra has no way to discover that after it's
already finalized a cell. (Bellman-Ford handles negative
weights, at a higher time cost, by not assuming any cell is truly finalized until every edge has been
relaxed V-1 times.)
The linear-scan priority queue above is slow. Finding the minimum by scanning
the whole array is O(V) per extraction, and there are up to V
extractions, so the queue operations alone cost O(V²). Swap it for the
binary heap from this site's heap entry — extract-min
drops to O(log V), push stays O(log V), and the whole algorithm falls to
O((V + E) log V). The demo above uses the simple version because the point of this
page is the algorithm's shape, not a heap implementation you've already seen; a real
distance-scale routing engine would use the heap.
It still only finds the cheapest path from one fixed source. Run it once and you get shortest distances from the start cell to everywhere reachable — not between every pair of cells. That's a different, harder problem (all-pairs shortest paths), solved by different algorithms entirely.
It has no notion of which direction the goal is in. The priority queue orders purely by accumulated cost, so Dijkstra explores outward evenly in every direction, discovering the end cell's true distance only once every cheaper cell everywhere else has already been finalized. If the goal is fixed and you have some estimate — even a rough one — of remaining distance, A* search biases that same priority queue toward the goal instead, and typically finalizes far fewer cells to find the exact same answer.
The priority queue is overkill if every edge costs exactly 0 or 1. That's a
narrow enough restriction to drop the heap entirely: 0-1
BFS gets the identical guarantee from a plain deque,
back at BFS's O(V + E) price instead of paying the log V factor a general
priority queue needs.
Time: O((V + E) log V) with a binary-heap priority queue — every
vertex is popped once (O(log V) each) and every edge triggers at most one push
(O(log V) each). The array-backed version in the demo and reference code above is
O(V² + E) instead, since each pop is a linear scan. On an r × c grid,
V = r·c and each cell has at most 4 edges, so this is O(r·c) vertices and
O(r·c) edges either way — the heap only changes the constant hiding inside the
log V factor, which matters once grids (or graphs) get large. Space:
O(V) for the distance array, the parent array, and the priority queue itself.
For a decision guide across all eleven of this site's shortest-path entries — which one to reach for depending on negative edges, single-source vs. all-pairs, and whether a heuristic is available — see Choosing a Shortest-Path Algorithm.