1
type WeightedGraph = [number, number][][];
2

3
function dijkstra(graph: WeightedGraph, start: number): number[] {
4
  const n = graph.length;
5
  const dist = new Array(n).fill(Infinity);
6
  const visited = new Array(n).fill(false);
7
  dist[start] = 0;
8

9
  for (let i = 0; i < n; i++) {
10
    let u = -1;
11
    for (let j = 0; j < n; j++) {
12
      if (!visited[j] && (u === -1 || dist[j] < dist[u])) u = j;
13
    }
14

15
    if (u === -1 || dist[u] === Infinity) break;
16
    visited[u] = true;
17

18
    for (const [v, weight] of graph[u]) {
19
      if (dist[u] + weight < dist[v]) {
20
        dist[v] = dist[u] + weight;
21
      }
22
    }
23
  }
24

25
  return dist;
26
}

1
class MinHeap {
2
  private heap: [number, number][] = [];
3

4
  push(item: [number, number]): void {
5
    this.heap.push(item);
6
    this.bubbleUp(this.heap.length - 1);
7
  }
8

9
  pop(): [number, number] | undefined {
10
    if (this.heap.length === 0) return undefined;
11
    if (this.heap.length === 1) return this.heap.pop();
12

13
    const top = this.heap[0];
14
    this.heap[0] = this.heap.pop()!;
15
    this.bubbleDown(0);
16
    return top;
17
  }
18

19
  get size(): number {
20
    return this.heap.length;
21
  }
22

23
  private bubbleUp(index: number): void {
24
    while (index > 0) {
25
      const parent = Math.floor((index - 1) / 2);
26
      if (this.heap[parent][1] <= this.heap[index][1]) break;
27
      [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
28
      index = parent;
29
    }
30
  }
31

32
  private bubbleDown(index: number): void {
33
    while (true) {
34
      const left = index * 2 + 1;
35
      const right = index * 2 + 2;
36
      let smallest = index;
37

38
      if (left < this.heap.length && this.heap[left][1] < this.heap[smallest][1]) smallest = left;
39
      if (right < this.heap.length && this.heap[right][1] < this.heap[smallest][1]) smallest = right;
40
      if (smallest === index) break;
41

42
      [this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
43
      index = smallest;
44
    }
45
  }
46
}
47

48
function dijkstraHeap(graph: WeightedGraph, start: number): number[] {
49
  const dist = new Array(graph.length).fill(Infinity);
50
  const heap = new MinHeap();
51
  dist[start] = 0;
52
  heap.push([start, 0]);
53

54
  while (heap.size > 0) {
55
    const [node, distance] = heap.pop()!;
56
    if (distance > dist[node]) continue;
57

58
    for (const [next, weight] of graph[node]) {
59
      const nextDistance = distance + weight;
60
      if (nextDistance < dist[next]) {
61
        dist[next] = nextDistance;
62
        heap.push([next, nextDistance]);
63
      }
64
    }
65
  }
66

67
  return dist;
68
}

1
function bellmanFord(edges: [number, number, number][], n: number, start: number): number[] {
2
  const dist = new Array(n).fill(Infinity);
3
  dist[start] = 0;
4

5
  for (let i = 0; i < n - 1; i++) {
6
    let updated = false;
7

8
    for (const [from, to, weight] of edges) {
9
      if (dist[from] !== Infinity && dist[from] + weight < dist[to]) {
10
        dist[to] = dist[from] + weight;
11
        updated = true;
12
      }
13
    }
14

15
    if (!updated) break;
16
  }
17

18
  for (const [from, to, weight] of edges) {
19
    if (dist[from] !== Infinity && dist[from] + weight < dist[to]) {
20
      throw new Error('存在负权环');
21
    }
22
  }
23

24
  return dist;
25
}

1
function floydWarshall(graph: number[][]): number[][] {
2
  const n = graph.length;
3
  const dist = graph.map(row => [...row]);
4

5
  for (let k = 0; k < n; k++) {
6
    for (let i = 0; i < n; i++) {
7
      for (let j = 0; j < n; j++) {
8
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
9
          dist[i][j] = dist[i][k] + dist[k][j];
10
        }
11
      }
12
    }
13
  }
14

15
  return dist;
16
}