Fewest hops isn't fastest
BFS finds the route with fewest roads, but roads take different times. Dijkstra's algorithm finds the quickest route when every road has a non-negative cost: always settle the closest unsettled place next, using a priority queue.
Dijkstra with a heap
const roads = [
["Cafe", "Lakeside", 4], ["Cafe", "Bazaar", 2], ["Bazaar", "Lakeside", 1],
["Lakeside", "Dam", 5], ["Bazaar", "Dam", 8], ["Dam", "Airport", 3], ["Lakeside", "Airport", 10],
];
class MinHeap {
a = [];
push(x) { const a = this.a; a.push(x); let i = a.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (a[p][0] <= a[i][0]) break; [a[p], a[i]] = [a[i], a[p]]; i = p; } }
pop() { const a = this.a, top = a[0], last = a.pop(); if (a.length) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < a.length && a[l][0] < a[m][0]) m = l; if (r < a.length && a[r][0] < a[m][0]) m = r; if (m === i) break; [a[m], a[i]] = [a[i], a[m]]; i = m; } } return top; }
get size() { return this.a.length; }
}
function dijkstra(roads, start) {
const graph = new Map();
for (const [a, b, w] of roads) {
if (!graph.has(a)) graph.set(a, []);
if (!graph.has(b)) graph.set(b, []);
graph.get(a).push([b, w]);
graph.get(b).push([a, w]);
}
const dist = new Map([[start, 0]]);
const prev = new Map();
const heap = new MinHeap();
heap.push([0, start]);
while (heap.size) {
const [d, node] = heap.pop();
if (d > dist.get(node)) continue;
for (const [next, w] of graph.get(node)) {
const nd = d + w;
if (nd < (dist.get(next) ?? Infinity)) {
dist.set(next, nd);
prev.set(next, node);
heap.push([nd, next]);
}
}
}
return { dist, prev };
}
const { dist, prev } = dijkstra(roads, "Cafe");
console.log(Object.fromEntries(dist));
const path = [];
for (let n = "Airport"; n; n = prev.get(n)) path.unshift(n);
console.log(path.join(" → "), dist.get("Airport"), "minutes");