演算法

1type Edge = [number, number, number]; // [u, v, weight]
2 
3function bellmanFord(n: number, edges: Edge[], source: number): { dist: number[]; negativeCycle: boolean } {
4  const dist = new Array(n).fill(Infinity);
5  dist[source] = 0;
6  for (let round = 1; round < n; round++) {
7    let changed = false;
8    for (const [u, v, w] of edges) {
9      if (dist[u] + w < dist[v]) {
10        dist[v] = dist[u] + w;
11        changed = true;
12      }
13    }
14    if (!changed) return { dist, negativeCycle: false };
15  }
16  // Still improving after n − 1 rounds: a negative cycle.
17  for (const [u, v, w] of edges) {
18    if (dist[u] + w < dist[v]) return { dist, negativeCycle: true };
19  }
20  return { dist, negativeCycle: false };
21}
22 
23function floydWarshall(n: number, edges: Edge[]): number[][] {
24  const d = Array.from({ length: n }, (_, i) =>
25    Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
26  for (const [u, v, w] of edges) d[u][v] = Math.min(d[u][v], w);
27  for (let k = 0; k < n; k++)
28    for (let i = 0; i < n; i++)
29      for (let j = 0; j < n; j++)
30        if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
31  return d; // a negative d[i][i] means a negative cycle through i
32}