loading
loading
loading
loading
Find the shortest distance from one start node to every other node in a weighted graph, by always finalizing the nearest unvisited node next and relaxing its edges.
Dijkstra's algorithm solves single-source shortest path on a weighted graph with non-negative edges: find the shortest distance from one start node to every other reachable node. It keeps a distance array (0 for the start, ∞ elsewhere) and repeatedly extracts the unvisited node with the smallest known distance from a priority queue — that distance is now provably final — then relaxes every edge out of it, updating a neighbor's distance whenever the path through the just-finalized node is shorter than what's currently recorded. It's really Graph Traversal's BFS pattern generalized to weighted edges, using a priority queue instead of a plain queue, and it's also a textbook greedy algorithm: the 'always extract the smallest' rule is exactly a greedy choice, provably correct because weights are never negative.
Step through dijkstra's algorithm live, one move at a time — this becomes a fully interactive visualizer.
Coming soonfunction dijkstra(graph, start) {
const distance = {};
const visited = new Set();
for (const node in graph) distance[node] = Infinity;
distance[start] = 0;
while (visited.size < Object.keys(graph).length) {
// Extract the unvisited node with the smallest distance.
// A real implementation uses a min-heap here — O(log n) instead of O(n).
let u = null;
for (const node in graph) {
if (visited.has(node) || distance[node] === Infinity) continue;
if (u === null || distance[node] < distance[u]) u = node;
}
if (u === null) break; // remaining nodes are unreachable
visited.add(u);
for (const { to, weight } of graph[u]) {
if (visited.has(to)) continue;
const candidate = distance[u] + weight;
if (candidate < distance[to]) distance[to] = candidate; // relax
}
}
return distance;
}// The efficient version: extract-min via a binary heap, O(log n) per
// extraction instead of an O(n) scan — see Heaps & Priority Queues.
function dijkstraWithHeap(graph, start, minHeap) {
const distance = {};
for (const node in graph) distance[node] = Infinity;
distance[start] = 0;
minHeap.insert(start, 0);
const visited = new Set();
while (!minHeap.isEmpty()) {
const u = minHeap.extractMin();
if (visited.has(u)) continue; // a stale, already-relaxed entry
visited.add(u);
for (const { to, weight } of graph[u]) {
const candidate = distance[u] + weight;
if (candidate < distance[to]) {
distance[to] = candidate;
minHeap.insert(to, candidate); // may insert a duplicate — the stale check above handles it
}
}
}
return distance;
}| BFS | Dijkstra's Algorithm | |
|---|---|---|
| Frontier structure | Plain queue (FIFO) | Priority queue, ordered by distance |
| Edge weights | Assumes uniform (or unweighted) | Arbitrary non-negative weights |
| Shortest path guarantee | Fewest edges | Lowest total weight |
| Time complexity | O(V + E) | O((V + E) log V) with a heap |
| A node's distance is final when... | ...it's first dequeued | ...it's extracted (smallest remaining) |
This is the crux of Dijkstra's correctness, and it's a greedy-choice-property argument (see Greedy Algorithms): the priority queue always extracts the unvisited node with the smallest current distance. Since every edge weight is non-negative, any path to that node through a still-unvisited node would have to pass through a node whose own distance is already ≥ the one being extracted — meaning that alternate path can't possibly be shorter. Once weights can be negative, this reasoning breaks entirely, which is exactly why Dijkstra requires non-negative weights and Bellman-Ford exists for graphs that don't have that guarantee.
'Relax edge (u, v)' means: if going through u offers a cheaper path to v than what's currently recorded, record that cheaper path. distance[v] = min(distance[v], distance[u] + weight(u, v)). A node's distance can be relaxed (lowered) many times while it's still unvisited — the first value it's assigned is rarely its final one. Only extraction (not relaxation) makes a distance permanent.
Using Dijkstra on a graph with negative edge weights — it will run without error and silently return wrong distances, since the 'extraction is final' guarantee depends on non-negativity. Forgetting to skip a node that's already visited when it's popped again from the priority queue (a node can be inserted multiple times as its distance keeps improving before it's finalized — the standard fix, shown in the heap-based example, is to check a visited set and skip stale entries rather than trying to decrease a key in place). And confusing Dijkstra with BFS on a graph that happens to have uniform weights, where they coincidentally agree — masking the bug until a differently-weighted graph is used.
Turn-by-turn navigation is single-source shortest path: the start is your current location, edge weights are road segment travel times (not just distances — a longer road can be faster), and the algorithm needs the shortest-time route to a destination. Network routers use the same shape of algorithm (often a Dijkstra variant) to find lowest-cost paths through a network, where edge weight represents latency or hop cost rather than physical distance. Any 'find the cheapest way from here to there, where cost isn't uniform per step' problem is a Dijkstra shape.
The 'always extract the smallest known distance next' rule is precisely a greedy choice — made once per node, never reconsidered, and provably correct because it satisfies the greedy choice property under non-negative weights (see the extraction-order deep dive above). Framing Dijkstra as 'BFS generalized with a priority queue' and as 'a greedy algorithm applied to shortest paths' are both correct descriptions of the same algorithm from two different angles.
Dijkstra explores uniformly outward by distance alone, with no sense of direction toward the target. A* adds a heuristic — an estimate of remaining distance to the goal (e.g., straight-line distance) — to prioritize nodes likely to be on the shortest path, often visiting far fewer nodes than Dijkstra for a single-target query. A* is not yet a topic on this platform, but it is a direct extension of exactly the extract-min-and-relax loop taught here.
The Pathfinding Visualizer runs breadth-first search on an unweighted grid — every move costs the same, so fewest-moves and lowest-cost coincide there by coincidence, not because BFS handles weights. The moment edges have different costs, BFS's guarantee no longer holds, which is exactly why this topic has its own dedicated Dijkstra's Algorithm Visualizer showing real weighted relaxation.
Dijkstra can produce wrong answers, silently — the 'extraction is final' guarantee assumes weights only make paths longer, never shorter. Graphs with negative weights (but no negative cycles) need the Bellman-Ford algorithm instead, which relaxes every edge repeatedly rather than relying on extraction order.
Both, accurately. It's Graph Traversal's BFS pattern generalized with a priority queue instead of a plain queue, and its correctness argument (extraction order gives a final answer) is a textbook greedy-choice-property proof — the two framings describe the same algorithm from different angles.
A plain scan for the smallest unvisited distance costs O(V) per extraction, giving O(V²) total. A binary heap (see Heaps & Priority Queues) does the same extraction in O(log V), dropping total time to O((V + E) log V) — a real asymptotic win on sparse graphs where E is much less than V².
Share what clicked for you and see notes from other learners on this topic.
Coming soon