Graphs
Dijkstra's Algorithm
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
// 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→DThe visited.has(node) check after popping matters. A node can sit in the queue several times at different costs; the first pop is the cheapest, and the rest are stale.
Recovering the path, not just the cost
Remembering where you came from
javascript
function dijkstraWithPath(graph, start, target) {
const distances = new Map([[start, 0]])
const previous = new Map()
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()
if (visited.has(node)) continue
visited.add(node)
if (node === target) break
for (const [next, weight] of graph.get(node) || []) {
const candidate = cost + weight
if (candidate < (distances.get(next) ?? Infinity)) {
distances.set(next, candidate)
previous.set(next, node)
queue.push({ node: next, cost: candidate })
}
}
}
// Walk the breadcrumbs backwards.
const path = []
let current = target
while (current !== undefined) {
path.unshift(current)
current = previous.get(current)
}
return { cost: distances.get(target), path }
}
console.log("dijkstraWithPath returns both the distances and the route taken")Negative weights break it
Dijkstra assumes that once a node is settled, no cheaper route to it can appear. A negative edge violates that - a later detour could reduce a cost you already finalised.
For negative weights use Bellman-Ford: O(nodes × edges) instead of O(edges log nodes), and it detects negative cycles, which have no meaningful shortest path at all.
Choosing
- Unweighted - BFS. Simpler and faster.
- Weighted, non-negative - Dijkstra.
- Negative weights - Bellman-Ford.
- All pairs - Floyd-Warshall, O(n cubed).
The assumption that makes it work
Dijkstra's relies on distances never decreasing as you move outward, which is only true when every edge weight is non-negative. One negative edge and the algorithm can finalise a node before finding a cheaper route to it - and it will not go back.
- All edges weight 1 - use BFS, it is simpler and faster.
- Non-negative weights - Dijkstra's, O((V + E) log V) with a heap.
- Negative weights - Bellman-Ford, O(V·E), and it detects negative cycles.
- All pairs, small graph - Floyd-Warshall, O(V³) and three tidy loops.
Dijkstra's with a priority queue
javascript
function shortestPaths(graph, start) {
// graph: Map<node, Array<[neighbour, weight]>>
const dist = new Map([[start, 0]])
const heap = [[0, start]] // stand-in PQ: fine for modest graphs
const done = new Set()
while (heap.length) {
heap.sort((a, b) => a[0] - b[0])
const [d, node] = heap.shift()
if (done.has(node)) continue
done.add(node)
for (const [next, weight] of graph.get(node) || []) {
const candidate = d + weight
if (candidate < (dist.get(next) ?? Infinity)) {
dist.set(next, candidate)
heap.push([candidate, next])
}
}
}
return dist
}
const demoGraph = new Map([["a", [["b", 1], ["c", 4]]], ["b", [["c", 2]]], ["c", []]])
console.log(shortestPaths(demoGraph, "a").get("c")) // 3The done set is what makes the lazy-deletion approach correct: a node can be pushed several times with different tentative distances, and only the first pop - the smallest - counts. Swap the sorted array for a real binary heap when the graph is large.