Dijkstra's Algorithm

Implement dijkstra(graph, source) — compute the shortest distance from source to every reachable vertex in a directed, non-negatively weighted graph. This is the algorithm behind GPS routing, network packet routing, and any "cheapest path" question where moving along an edge costs something. On unit-weighted graphs, breadth-first search already does this; once edges carry different costs, you need Dijkstra's algorithm — BFS upgraded with a priority queue that always expands the nearest unsettled vertex next.

Signature

// graph: Map<VertexId, Array<{ to: VertexId, weight: number }>>
//   Adjacency list with weights. Weights are non-negative numbers
//   (Dijkstra's correctness depends on this — see Notes).
// source: VertexId — the starting vertex.
// returns: Map<VertexId, number>
//   Shortest distance from source to each REACHABLE vertex.
//   Unreachable vertices are NOT in the result Map.
function dijkstra(graph, source): Map<VertexId, number>;

VertexId can be any value you can use as a Map/Set key (string, number).

Examples

// Linear chain: A → B (5) → C (2)
const g1 = new Map([
  ['A', [{ to: 'B', weight: 5 }]],
  ['B', [{ to: 'C', weight: 2 }]],
  ['C', []],
]);
dijkstra(g1, 'A'); // → Map { A => 0, B => 5, C => 7 }

// Triangle with a shortcut: the indirect path A → C → B beats the direct A → B.
const g2 = new Map([
  ['A', [{ to: 'B', weight: 10 }, { to: 'C', weight: 3 }]],
  ['B', []],
  ['C', [{ to: 'B', weight: 2 }]],
]);
dijkstra(g2, 'A'); // → Map { A => 0, C => 3, B => 5 }

// X is unreachable from A — it is NOT in the result Map at all.
const g3 = new Map([
  ['A', [{ to: 'B', weight: 1 }]],
  ['B', []],
  ['X', [{ to: 'A', weight: 1 }]],
]);
dijkstra(g3, 'A'); // → Map { A => 0, B => 1 }   (no X key)

// Single-vertex graph with no edges.
dijkstra(new Map([['A', []]]), 'A'); // → Map { A => 0 }

Notes

• Non-negative weights are required. Dijkstra is greedy: once a vertex is settled, its distance is final. A negative edge could lower a settled vertex's distance after the fact, breaking that invariant. For negative edges use Bellman-Ford.
• The result is a Map, not an object. Vertex ids may be numbers or strings; a Map keeps them distinct and ordered by insertion.
• Unreachable vertices are omitted from the result. Callers who prefer a default can use result.get(v) ?? Infinity at the call site.
• The source maps to 0. Even if the source has a self-loop with positive weight, the shortest distance to itself is zero.
• Ties in distance still produce a unique distance map. Multiple shortest paths can exist; the distances themselves are well-defined.
• Don't worry about path reconstruction (returning the actual sequence of vertices), undirected graphs (caller can mirror edges), or negative weights — those are out of scope.