Dijkstra's algorithm

O(E log V)

Keep a best-known cost per node, settle the cheapest unsettled node on each step, and relax its edges to lower neighbors' costs. Because all weights are non-negative, a node's cost is final the moment it is settled.

Signals

cheapest/shortest path with weighted edgesnon-negative edge weightsminimum total cost to reach every nodenetwork delay time / route cost, not fewest roadsweighted graph, single-source shortest paths

Template

function dijkstra(n, adj, source) {
    const dist = new Array(n).fill(Infinity);
    dist[source] = 0;
    const heap = [[0, source]]; // [distance, node]
    while (heap.length) {
        heap.sort((a, b) => a[0] - b[0]); // swap for a real heap in production
        const [d, u] = heap.shift();
        if (d > dist[u]) continue;
        for (const [v, w] of adj[u] || []) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                heap.push([dist[v], v]);
            }
        }
    }
    return dist;
}

Looks similar, isn't

Graph BFS / DFS: BFS counts unweighted steps and assumes every edge costs the same. Dijkstra is for weighted, non-negative edges, where three cheap edges can beat two expensive ones, so hop count alone is the wrong answer.

V, E up to ~1e5, non-negative edge weights, need cheapest path not fewest hops -> O(E log V) with a min-heap settling one node per pop.

Learn this pattern