Bellman-Ford Algorithm

1function bellmanFord(vertices, edges, source) {
2  const dist = new Array(vertices).fill(Infinity);
3  dist[source] = 0;
4 
5  // Step 1: Relax all edges (V - 1) times
6  for (let i = 1; i <= vertices - 1; i++) {
7    for (const [u, v, w] of edges) {
8      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
9        dist[v] = dist[u] + w;
10      }
11    }
12  }
13 
14  // Step 2: Check for negative-weight cycles
15  for (const [u, v, w] of edges) {
16    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
17      throw new Error("Graph contains a negative weight cycle!");
18    }
19  }
20 
21  return dist;
22}
23 
24// Example usage:
25// 5 vertices (0 to 4), edges [u, v, weight]
26// const edges = [
27//   [0, 1, -1], [0, 2, 4],
28//   [1, 2, 3],  [1, 3, 2], [1, 4, 2],
29//   [3, 2, 5],  [3, 1, 1],
30//   [4, 3, -3]
31// ];
32// bellmanFord(5, edges, 0); // Returns [0, -1, 2, -1, 1]