Graphs

Dijkstra's Algorithm

Written by Swapnil RajaPublished 28 Aug 2026

BFS finds the fewest hops. Dijkstra finds the lowest cost. The moment your edges carry a weight - distance, price, latency - BFS starts giving confidently wrong answers.

Why BFS is not enough

BFS assumes every edge costs the same. With weights, a two-hop route can easily be cheaper than a one-hop route, and BFS will return the one-hop.

The idea

Always expand the cheapest node reached so far. Because you take the cheapest first, the first time you settle a node you have its final answer. That is BFS with a priority queue instead of a plain one.

Dijkstra

javascript

PreviousTopological Sort NextUnion-Find (Disjoint Sets)

// From the Heaps lesson, repeated so this example runs on its own. class PriorityQueue { items = [] constructor(compare = (a, b) => a - b) { this.compare = compare } get size() { return this.items.length } push(v) { this.items.push(v) let i = this.items.length - 1 while (i > 0) { const p = (i - 1) >> 1 if (this.compare(this.items[p], this.items[i]) <= 0) break ;[this.items[p], this.items[i]] = [this.items[i], this.items[p]] i = p } } pop() { if (!this.items.length) return undefined const top = this.items[0] const last = this.items.pop() if (this.items.length) { this.items[0] = last let i = 0 while (true) { const l = 2 * i + 1, r = 2 * i + 2 let s = i if (l < this.items.length && this.compare(this.items[l], this.items[s]) < 0) s = l if (r < this.items.length && this.compare(this.items[r], this.items[s]) < 0) s = r if (s === i) break ;[this.items[i], this.items[s]] = [this.items[s], this.items[i]] i = s } } return top } } function dijkstra(graph, start) { // graph: Map<node, Array<[neighbour, weight]>> const distances = new Map() for (const node of graph.keys()) distances.set(node, Infinity) distances.set(start, 0) const visited = new Set() const queue = new PriorityQueue((a, b) => a.cost - b.cost) queue.push({ node: start, cost: 0 }) while (queue.size) { const { node, cost } = queue.pop() // Stale entry — we already settled this one more cheaply. if (visited.has(node)) continue visited.add(node) for (const [next, weight] of graph.get(node) || []) { if (visited.has(next)) continue const candidate = cost + weight if (candidate < distances.get(next)) { distances.set(next, candidate) queue.push({ node: next, cost: candidate }) } } } return distances } const graph = new Map([ ["A", [["B", 1], ["C", 4]]], ["B", [["C", 2], ["D", 5]]], ["C", [["D", 1]]], ["D", []], ]) console.log(dijkstra(graph, "A")) // A:0, B:1, C:3, D:4 — A→B→C→D beats A→C→D and A→B→D

Dijkstra's Algorithm

Why BFS is not enough

The idea

Recovering the path, not just the cost

Negative weights break it

Choosing