Advanced Graph Algorithms (Dijkstra, Topological Sort, Union-Find)

1// DIJKSTRA — Shortest path with weights
2function dijkstra(graph, start) {
3  const dist = new Map();
4  const heap = new MinHeap(); // [distance, node]
5
6  dist.set(start, 0);
7  heap.push([0, start]);
8
9  while (heap.size()) {
10    const [d, u] = heap.pop();
11    if (d > (dist.get(u) ?? Infinity)) continue; // Skip outdated
12
13    for (const [v, w] of graph.get(u) || []) {
14      const newDist = d + w;
15      if (newDist < (dist.get(v) ?? Infinity)) {
16        dist.set(v, newDist);
17        heap.push([newDist, v]);
18      }
19    }
20  }
21  return dist;
22}
23
24// TOPOLOGICAL SORT — Kahn's (BFS with in-degrees)
25function topologicalSort(n, edges) {
26  const graph = new Map();
27  const inDegree = new Array(n).fill(0);
28  for (let i = 0; i < n; i++) graph.set(i, []);
29  for (const [u, v] of edges) {
30    graph.get(u).push(v);
31    inDegree[v]++;
32  }
33
34  const queue = [];
35  for (let i = 0; i < n; i++) {
36    if (inDegree[i] === 0) queue.push(i);
37  }
38
39  const order = [];
40  while (queue.length) {
41    const node = queue.shift();
42    order.push(node);
43    for (const neighbor of graph.get(node)) {
44      inDegree[neighbor]--;
45      if (inDegree[neighbor] === 0) queue.push(neighbor);
46    }
47  }
48
49  return order.length === n ? order : []; // Empty if cycle exists
50}
51
52// UNION-FIND with path compression + union by rank
53class UnionFind {
54  constructor(n) {
55    this.parent = Array.from({length: n}, (_, i) => i);
56    this.rank = new Array(n).fill(0);
57    this.components = n;
58  }
59
60  find(x) {
61    if (this.parent[x] !== x) {
62      this.parent[x] = this.find(this.parent[x]); // Path compression
63    }
64    return this.parent[x];
65  }
66
67  union(x, y) {
68    const px = this.find(x), py = this.find(y);
69    if (px === py) return false; // Already connected
70    // Union by rank
71    if (this.rank[px] < this.rank[py]) this.parent[px] = py;
72    else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
73    else { this.parent[py] = px; this.rank[px]++; }
74    this.components--;
75    return true;
76  }
77
78  connected(x, y) { return this.find(x) === this.find(y); }
79}
80
81// COURSE SCHEDULE — Can you finish all courses? (Cycle detection in DAG)
82function canFinish(numCourses, prerequisites) {
83  return topologicalSort(numCourses, prerequisites).length === numCourses;
84}
85
86// NETWORK DELAY TIME — Dijkstra on directed weighted graph
87function networkDelayTime(times, n, k) {
88  const graph = new Map();
89  for (let i = 1; i <= n; i++) graph.set(i, []);
90  for (const [u, v, w] of times) graph.get(u).push([v, w]);
91
92  const dist = dijkstra(graph, k);
93  if (dist.size < n) return -1; // Not all reachable
94  return Math.max(...dist.values());
95}