Floyd-Warshall Algorithm: Finding All-Pairs Shortest Paths

The Floyd-Warshall algorithm is a dynamic programming algorithm used to find the shortest paths between all pairs of vertices in a weighted graph. This article will provide a comprehensive explanation of the algorithm, its implementation, complexity analysis, and alternative approaches.

Fundamental Concepts / Prerequisites

Before diving into the Floyd-Warshall algorithm, it's helpful to have a basic understanding of the following:

• Graphs: Knowledge of graph representation (adjacency matrices, adjacency lists), vertices, and edges.
• Weighted Graphs: Graphs where edges have associated weights (costs or distances).
• Dynamic Programming: Understanding the principle of breaking down a problem into smaller overlapping subproblems and solving them optimally.
• Adjacency Matrix: A 2D array representing the graph, where `matrix[i][j]` stores the weight of the edge between vertex `i` and vertex `j`. If there is no edge, it typically holds a value representing infinity.

Implementation in C++

#include <iostream>
#include <vector>
#include <algorithm> // For std::min and std::numeric_limits

using namespace std;

// Function to implement Floyd-Warshall algorithm
void floydWarshall(vector<vector<int>>& graph) {
  int V = graph.size(); // Number of vertices
  int INF = numeric_limits<int>::max(); // Represents infinity

  // Iterate through all vertices as intermediate vertices
  for (int k = 0; k < V; ++k) {
    // Iterate through all vertices as source vertices
    for (int i = 0; i < V; ++i) {
      // Iterate through all vertices as destination vertices
      for (int j = 0; j < V; ++j) {
        // If vertex k is on the shortest path from i to j, then update the value of graph[i][j]
        if (graph[i][k] != INF && graph[k][j] != INF && graph[i][k] < INF / 2 && graph[k][j] < INF/2) {
            if (graph[i][j] > graph[i][k] + graph[k][j]) {
                graph[i][j] = graph[i][k] + graph[k][j];
            }
        }

      }
    }
  }

  // Print the shortest distance matrix
  cout << "Shortest distances between every pair of vertices:\n";
  for (int i = 0; i < V; ++i) {
    for (int j = 0; j < V; ++j) {
      if (graph[i][j] == INF)
        cout << "INF ";
      else
        cout << graph[i][j] << "   ";
    }
    cout << endl;
  }
}

int main() {
  // Example graph represented as an adjacency matrix
  vector<vector<int>> graph = {
    {0,   5,   INF, 10},
    {INF, 0,   3,   INF},
    {INF, INF, 0,   1},
    {INF, INF, INF, 0}
  };

  floydWarshall(graph);

  return 0;
}

Code Explanation

The C++ code implements the Floyd-Warshall algorithm as follows:

1. `floydWarshall(vector<vector<int>>& graph)`: This function takes the adjacency matrix representation of the graph as input.

2. `int V = graph.size();`: Gets the number of vertices in the graph.

3. `int INF = numeric_limits<int>::max();`: Defines a constant `INF` to represent infinity. This is used for edges that don't exist or have infinite weight.

4. Outer Loop (`for (int k = 0; k < V; ++k)`): This loop iterates through each vertex `k`, considering it as an intermediate vertex in potential shortest paths.

5. Nested Loops (`for (int i = 0; i < V; ++i)` and `for (int j = 0; j < V; ++j)`): These loops iterate through all possible source vertices `i` and destination vertices `j`.

6. `if (graph[i][k] != INF && graph[k][j] != INF && graph[i][k] < INF / 2 && graph[k][j] < INF/2)`: This condition checks if a path from `i` to `k` and from `k` to `j` exists (i.e., the weights are not infinity) to avoid overflow during addition.

7. `if (graph[i][j] > graph[i][k] + graph[k][j])`: Checks if the current shortest distance between `i` and `j` is greater than the distance obtained by going through `k`.

8. `graph[i][j] = graph[i][k] + graph[k][j];`: If the path through `k` is shorter, the shortest distance matrix `graph[i][j]` is updated.

9. Printing the Result: After the loops complete, the `graph` matrix contains the shortest path distances between all pairs of vertices, which are printed to the console.

Complexity Analysis

The Floyd-Warshall algorithm has the following complexities:

• Time Complexity: O(V³), where V is the number of vertices. This is because the algorithm consists of three nested loops, each iterating through the vertices.
• Space Complexity: O(V²), where V is the number of vertices. This is due to the space required to store the adjacency matrix representing the graph. The algorithm operates in-place, meaning it modifies the existing adjacency matrix, so no additional significant memory is allocated.

Alternative Approaches

An alternative approach to finding all-pairs shortest paths is to use Dijkstra's algorithm repeatedly. Dijkstra's algorithm finds the shortest paths from a single source vertex to all other vertices in a graph. By running Dijkstra's algorithm for each vertex as the source, you can achieve the same result as the Floyd-Warshall algorithm.

Trade-offs:

• Dijkstra's algorithm with binary heap has a time complexity of O(V * (E + V log V)) for finding all-pairs shortest paths, where E is the number of edges. This can be more efficient than Floyd-Warshall for sparse graphs (where E is much smaller than V²).
• Dijkstra's algorithm doesn't handle negative edge weights directly without modifications, while Floyd-Warshall can detect negative cycles. However, the provided implementation would overflow in the presence of negative cycles.

Conclusion

The Floyd-Warshall algorithm is a powerful and versatile algorithm for finding the shortest paths between all pairs of vertices in a weighted graph. Its simplicity and ease of implementation make it a valuable tool for various applications, especially when dealing with dense graphs and graphs without negative cycles. Understanding its time and space complexity allows developers to make informed decisions about its suitability for specific problem scenarios. If the graph is sparse, Dijkstra's algorithm ran for each vertex might be more performant.