Bellman-Ford & Floyd-Warshall (Introduction)

Bellman-Ford & Floyd-Warshall

Welcome! While Dijkstra's algorithm is efficient, it has its limits. What if a graph has negative edge weights? Or what if you need to find the shortest paths between all pairs of vertices? For these scenarios, we turn to two powerful algorithms: Bellman-Ford and Floyd-Warshall.

---

1. Bellman-Ford Algorithm

The Bellman-Ford algorithm finds the shortest paths from a single source vertex to all other vertices, just like Dijkstra. However, it has the crucial ability to handle graphs with negative edge weights.

1.1. The Core Idea: Relaxing All Edges

Instead of a greedy approach, Bellman-Ford uses a more methodical process. It repeatedly relaxes every single edge in the graph. A single pass of relaxing all edges will find all shortest paths of length 1. A second pass will find all shortest paths of length 2, and so on. Since the longest possible simple path in a graph with N vertices has N-1 edges, repeating this process N-1 times guarantees finding the shortest path.

1.2. The Algorithm Step-by-Step

1. Initialization:

   • Create a distances array. Set the source distance to 0 and all others to infinity.

2. Relaxation Loops:

   • Repeat N-1 times:
     • For each edge (u, v) with weight w in the graph:
       • If distances[u] + w < distances[v], update distances[v] = distances[u] + w.

3. Negative Cycle Detection:

   • After N-1 iterations, perform one more (the Nth) iteration:
     • For each edge (u, v) with weight w:
       • If distances[u] + w < distances[v], it means a shorter path can still be found. This is only possible if a negative-weight cycle exists.

1.3. Implementation

function bellmanFord(N, edges, src) {
  const dist = Array(N).fill(Infinity);
  dist[src] = 0;

  // Relax edges N-1 times
  for (let i = 0; i < N - 1; i++) {
    for (const { u, v, w } of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }

  // Check for negative cycles
  for (const { u, v, w } of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
      throw new Error("Graph contains a negative-weight cycle");
    }
  }

  return dist;
}

1.4. Complexity Analysis

• Time Complexity: O(N * M), where N is the number of vertices and M is the number of edges.
• Space Complexity: O(N) to store distances.

---

2. Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is designed for a different problem: finding the All-Pairs Shortest Paths (APSP). It calculates the shortest path between every single pair of vertices in the graph.

2.1. The Core Idea: Dynamic Programming

Floyd-Warshall uses a dynamic programming approach. It considers all possible vertices as "intermediate" nodes in a path. It iteratively builds up a solution by asking, "Can we find a shorter path from vertex i to vertex j by going through vertex k?"

2.2. The Algorithm Step-by-Step

1. Initialization:

   • Create an N x N matrix dist where dist[i][j] is the weight of the edge from i to j, or infinity if no direct edge exists. dist[i][i] should be 0.

2. Main Loops:

   • For each vertex k from 0 to N-1 (as the intermediate vertex):
     • For each vertex i from 0 to N-1 (as the start vertex):
       • For each vertex j from 0 to N-1 (as the end vertex):
         • Update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

3. Completion:

   • After the loops complete, the dist matrix will contain the shortest path distances between all pairs of vertices.

2.3. Implementation

function floydWarshall(N, initialDist) {
  const dist = initialDist; // Make a copy if you need to preserve the original

  for (let k = 0; k < N; k++) {
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
        if (dist[i][k] !== Infinity && dist[k][j] !== Infinity) {
          dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        }
      }
    }
  }

  return dist;
}

2.4. Complexity Analysis

• Time Complexity: O(N^3), due to the three nested loops.
• Space Complexity: O(N^2) to store the distance matrix.

---

Key Takeaway:

• Use Bellman-Ford for single-source shortest paths when you have negative edge weights.
• Use Floyd-Warshall when you need to find the shortest paths between all pairs of vertices, especially in dense graphs where its O(N^3) complexity is acceptable.