Floyd-Warshall Algorithm

---

The Floyd-Warshall Algorithm is a classic algorithm used to find the shortest paths between all pairs of vertices in a weighted graph. It is especially useful in dense graphs and is applicable to both directed and undirected graphs. The algorithm uses a dynamic programming approach to iteratively improve the estimation of shortest paths.

Given a graph with n vertices, the Floyd-Warshall algorithm calculates the shortest paths between every pair of vertices. The result is stored in a distance matrix where the value at row i and column j represents the shortest distance between vertex i and vertex j.

How the Floyd-Warshall Algorithm Works

The core idea of the Floyd-Warshall algorithm is based on the principle of dynamic programming, where we incrementally build the solution by considering intermediate vertices.

The algorithm iterates through all pairs of vertices and attempts to improve the shortest path by checking if a path through an intermediate vertex offers a shorter path.

Floyd-Warshall Algorithm Pseudocode:

1. Let dist[][] be a 2D array where dist[i][j] holds the shortest distance from vertex i to vertex j.

2. Initialize dist[i][j] to the weight of the edge from i to j. If no direct edge exists, set it to infinity (∞), except for dist[i][i] which is 0.

3. For each vertex k, update the shortest path between every pair of vertices i and j by checking if going through k offers a shorter path:

   $$dist[i][j]=\min (dist[i][j],dist[i][k]+dist[k][j])$$

4. After running the algorithm, dist[i][j] will contain the shortest distance between vertices i and j.

Steps of the Floyd-Warshall Algorithm

1. Initialization: Set the initial distances based on direct edges.
2. Iteration: For each possible intermediate vertex, update the distances between all pairs of vertices.
3. Termination: After completing the iterations, the shortest distances are stored in the dist matrix.

---

Floyd-Warshall Algorithm Example

Let's consider a graph with 4 vertices and the following weighted adjacency matrix:

    0   5   ∞   10
    ∞   0   3   ∞
    ∞   ∞   0   1
    ∞   ∞   ∞   0

Where:

• 0 indicates the distance from a vertex to itself.
• ∞ (infinity) indicates no direct edge between the vertices.

After applying the Floyd-Warshall algorithm, the shortest distance matrix will look like this:

    0   5   8   9
    ∞   0   3   4
    ∞   ∞   0   1
    ∞   ∞   ∞   0

Floyd-Warshall Algorithm Implementation in Python

INF = float('inf')

def floyd_warshall(graph):
    # Get the number of vertices
    n = len(graph)
    
    # Initialize the distance matrix
    dist = [row[:] for row in graph]
    
    # Floyd-Warshall algorithm
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

# Example graph (adjacency matrix)
graph = [
    [0, 5, INF, 10],
    [INF, 0, 3, INF],
    [INF, INF, 0, 1],
    [INF, INF, INF, 0]
]

# Run Floyd-Warshall Algorithm
result = floyd_warshall(graph)

# Print the result
for row in result:
    print(row)

Explanation:

• The graph is represented as an adjacency matrix, where INF denotes that no direct edge exists between two vertices.
• We use a 3-level nested loop to apply the Floyd-Warshall algorithm. The outer loop iterates through each intermediate vertex k, and the inner loops check each pair of vertices (i, j) and update the distance matrix.

Floyd-Warshall Algorithm Implementation in C++

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

#define INF INT_MAX

void floydWarshall(vector<vector<int>>& graph) {
    int n = graph.size();

    // Initialize the distance matrix
    vector<vector<int>> dist = graph;

    // Floyd-Warshall algorithm
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // Print the distance matrix
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INF) {
                cout << "INF ";
            } else {
                cout << dist[i][j] << " ";
            }
        }
        cout << endl;
    }
}

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

    // Run Floyd-Warshall algorithm
    floydWarshall(graph);

    return 0;
}

Explanation:

• The graph is represented as an adjacency matrix, where INF (set to INT_MAX in C++) represents an absence of an edge.
• The three nested loops implement the Floyd-Warshall algorithm to update the shortest paths.

---

Time and Space Complexity of Floyd-Warshall Algorithm

• Time Complexity:
  The algorithm involves three nested loops over the vertices, resulting in a time complexity of O(n³), where n is the number of vertices. This is because, for each pair of vertices (i, j), we check if the shortest path can be improved by going through an intermediate vertex k.

• Space Complexity:
  The space complexity is O(n²) because we store the distance matrix, which has dimensions of n x n.

---

Applications of Floyd-Warshall Algorithm

1. All-Pairs Shortest Path Problem:

   • The Floyd-Warshall algorithm is used when we need the shortest paths between all pairs of vertices in a graph. This is useful in network routing, transportation systems, and various optimization problems.

2. Graph Transitive Closure:

   • The Floyd-Warshall algorithm can be adapted to compute the transitive closure of a graph, which determines whether a path exists between two vertices.

3. Negative Weight Cycle Detection:

   • By applying the Floyd-Warshall algorithm, we can detect negative weight cycles in a graph. If any diagonal element of the final distance matrix becomes negative, a negative weight cycle exists.

4. Network Flow Problems:

   • The algorithm can be used in various network flow problems where we need to find the shortest paths between all pairs of nodes.

---

---