Dijkstra Shortest Path Template

Dijkstra's algorithm finds the shortest path from a source to every reachable node in a weighted graph with non-negative edge weights. The textbook O((V + E) log V) implementation pairs a min-heap with a relaxation loop. This snippet covers the heap-based template, a parent-tracking variant that reconstructs the actual path, and an early-exit form for single-target queries.

JavaScript

Hard

algorithms

dijkstra

code-template

heap

1,111 views

Heap-based Dijkstra

Ask AI

class MinHeap {
    constructor() { this.data = []; }
    push(item) {
        this.data.push(item);
        let i = this.data.length - 1;
        while (i > 0) {
            const p = (i - 1) >>> 1;
            if (this.data[i][0] < this.data[p][0]) {
                [this.data[i], this.data[p]] = [this.data[p], this.data[i]];
                i = p;
            } else break;
        }
    }
    pop() {
        const top = this.data[0];
        const last = this.data.pop();
        if (this.data.length > 0) {
            this.data[0] = last;
            let i = 0;
            const n = this.data.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < n && this.data[l][0] < this.data[s][0]) s = l;
                if (r < n && this.data[r][0] < this.data[s][0]) s = r;
                if (s === i) break;
                [this.data[i], this.data[s]] = [this.data[s], this.data[i]];
                i = s;
            }
        }
        return top;
    }
    get size() { return this.data.length; }
}

function dijkstra(graph, source) {
    const dist = new Map();
    for (const node of Object.keys(graph)) dist.set(node, Infinity);
    dist.set(source, 0);
    const heap = new MinHeap();
    heap.push([0, source]);
    while (heap.size > 0) {
        const [d, u] = heap.pop();
        if (d > dist.get(u)) continue;
        for (const [v, w] of graph[u]) {
            const alt = d + w;
            if (alt < dist.get(v)) {
                dist.set(v, alt);
                heap.push([alt, v]);
            }
        }
    }
    return dist;
}

const g = { A: [['B', 4], ['C', 1]], B: [['D', 1]], C: [['B', 2], ['D', 5]], D: [] };
console.log([...dijkstra(g, 'A').entries()]);

Each iteration pops the node with the smallest tentative distance from the heap, then relaxes its outgoing edges: if going through the current node beats the previously known distance to a neighbor, record the better distance and push the neighbor with its new key. The key insight is that the first time a node is popped, its distance is final, because non-negative weights mean no later path can be shorter. The if (d > dist.get(u)) continue guard skips stale heap entries from earlier pushes; this is cheaper than implementing decrease-key. Total cost is O((V + E) log V).

2 more snippets in this entry are available for premium members.

Upgrade to Premium

Back to Code Snippets