TypeScriptdijkstra.ts
Copy
1
type WGraph = Map<string, [string, number][]>;
2
 
3
function dijkstra(graph: WGraph, start: string): Map<string, number> {
4
  const dist = new Map<string, number>();
5
  const visited = new Set<string>();
6
 
7
  for (const node of graph.keys()) dist.set(node, Infinity);
8
  dist.set(start, 0);
9
 
10
  while (true) {
11
    // Find unvisited node with min distance (O(V) — use heap for better perf)
12
    let u: string | null = null;
13
    for (const [node, d] of dist) {
14
      if (!visited.has(node) && (u === null || d < dist.get(u)!)) u = node;
15
    }
16
    if (u === null || dist.get(u) === Infinity) break;
17
 
18
    visited.add(u);
19
    for (const [v, weight] of graph.get(u) ?? []) {
20
      const newDist = dist.get(u)! + weight;
21
      if (newDist < dist.get(v)!) dist.set(v, newDist);
22
    }
23
  }
24
  return dist;
25
}
26
 
27
// Test graph: A-B(4), A-C(1), C-B(2), B-D(1)
28
const graph: WGraph = new Map([
29
  ['A', [['B', 4], ['C', 1]]],
30
  ['B', [['D', 1]]],
31
  ['C', [['B', 2]]],
32
  ['D', []],
33
]);
34
const distances = dijkstra(graph, 'A');
35
console.log([...distances.entries()]);
36
// A:0, B:3 (A→C→B), C:1, D:4