Dijkstra’s algorithm

The cost of a route

A weighted graph assigns a cost to every edge: time, distance or another additive quantity. A route’s cost is the sum of its edge weights. In this example edges work in both directions and every weight is nonnegative.

BFS minimizes transitions: S → A → G takes two edges but costs 8 + 1 = 9. Dijkstra finds S → B → C → G: three edges costing 1 + 1 + 2 = 4. Both are valid routes, but they optimize different quantities. With every weight equal to one, minimum cost and minimum transition count coincide.

Select the minimum, then relax edges

Initially d(S)=0 and all other distances are infinity. The frontier holds discovered, unselected vertices. Select the smallest d across the entire frontier. Ties keep first discovery order; neighbor order follows the input edge list.

For a neighbor v of the selected u, try candidate = d(u) + weight(u,v). If it is smaller than d(v), replace the distance and parent. This is relaxation. A first discovery adds v to the frontier; an improvement updates its priority in place. Equal costs keep the existing parent.

Here A is discovered with distance 8. After B is selected, the route S → B → A costs 4, so A’s distance drops from 8 to 4 and its parent becomes B. A previously discovered vertex must not be ignored simply because it is already in the frontier.

Why a selected distance is final

The smallest tentative distance is final when its vertex is selected: any route through a still-unselected vertex starts with a cost at least this large, and nonnegative remaining edges cannot lower it. Once all neighbors have been checked, the vertex is settled and need not be reopened.

Stop when G is selected, not when it is first discovered. Follow parents back to S to reconstruct the route. If the frontier becomes empty, G is unreachable. A start equal to the goal gives cost zero and a one-vertex route. Zero weights are allowed; negative weights are rejected before search. Finite sums must fit JavaScript Number; the implementation rejects overflow.

This page uses Dijkstra with early termination at one goal, also called uniform-cost search. Unlike Greedy it does not prioritize h. Unlike A* it does not add h: using h=0 in A* gives the same distance priority.

Reading the player

Edge numbers are fixed prices; d below each vertex is the best known cost from S, not an estimate to G. Purple marks the frontier, an outline marks the selected vertex, and green marks the reconstructed route. The text lists distances and frontier even without reading the canvas.

Selected counts frontier removals, including G. Neighbor checks count adjacency entries inspected, including settled neighbors; G’s neighbors are not inspected. Improved finite distances counts decreases after first discovery, excluding infinity-to-finite updates. Reconstruction grows backwards and is reversed in the final snapshot. Distance values outside the selected set may still be tentative when the goal is reached.

Try equal weights, an isolated goal and start equal to goal. Play, pause, step backwards and forwards, restart or seek to any event. Playback uses discrete states without motion.

The cost of this implementation

For V vertices and E adjacency entries, an array frontier gives O(V² + E) time and O(V) search memory excluding the graph. Minimum selection and removal cost O(V); each vertex is selected at most once. A binary heap with decrease-key can instead give O((V+E) log V), but this demonstration scans an array.

Visualization makes one immutable graph copy, O(V+E), and saves O(V) data per event. There are O(V+E) events, so saved history uses O(V(V+E)) memory in addition to the graph. This replay cost is separate from algorithm working memory.

JavaScript implementation

adjacency is an array of arrays of {to, weight}, with integer vertex IDs from 0 to V−1. Add both directions for each undirected edge, in input order, to reproduce this player. The input is unchanged; the result contains a path and its cost, or null. The function also works for directed graphs. All weights must be finite and nonnegative; sums must remain finite.

function dijkstra(adjacency, start, goal) {
    const n = adjacency.length;
    const valid = v => Number.isInteger(v) && v >= 0 && v < n;
    if (!valid(start) || !valid(goal)) throw Error("Invalid endpoint");
    for (const neighbors of adjacency) {
        for (const { to, weight } of neighbors) {
            if (!valid(to) || !Number.isFinite(weight) || weight < 0)
                throw Error("Expected finite nonnegative weights");
        }
    }
    const distance = Array(n).fill(Infinity);
    const parent = Array(n).fill(null);
    const settled = new Set(), open = [start];
    distance[start] = 0;
    while (open.length) {
        let best = 0;
        for (let i = 1; i < open.length; i++)
            if (distance[open[i]] < distance[open[best]]) best = i;
        const current = open.splice(best, 1)[0];
        if (current === goal) {
            const path = [];
            for (let v = goal; v !== null; v = parent[v]) path.push(v);
            return { path: path.reverse(), cost: distance[goal] };
        }
        settled.add(current);
        for (const { to, weight } of adjacency[current]) {
            const candidate = distance[current] + weight;
            if (!Number.isFinite(candidate)) throw Error("Path cost overflow");
            if (settled.has(to) || candidate >= distance[to]) continue;
            if (distance[to] === Infinity) open.push(to);
            distance[to] = candidate;
            parent[to] = current;
        }
    }
    return null;
}