Floyd-Warshall Algorithm

Description

The Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in a weighted graph. It can handle both positive and negative edge weights, but not negative cycles. The algorithm works by incrementally improving an estimate on the shortest path between two vertices by considering if using an intermediate vertex would create a shorter path.

• Finds shortest paths between all pairs of vertices
• Works with both directed and undirected graphs
• Can handle negative edge weights (but not negative cycles)
• Uses dynamic programming approach

How It Works

1. Initialize the distance matrix:
   • Set distance[i][j] = weight of edge (i,j) if it exists
   • Set distance[i][j] = ∞ if no direct edge exists
   • Set distance[i][i] = 0 for all vertices
2. For each vertex k as intermediate:
   • For each pair of vertices (i,j):
   • If distance[i][j] > distance[i][k] + distance[k][j]
   • Update distance[i][j] = distance[i][k] + distance[k][j]
3. After all iterations:
   • distance[i][j] contains the shortest path length from i to j
   • Check diagonal elements for negative cycles

Visualization

Implementation

def floyd_warshall(graph):
    V = len(graph)
    dist = [[float('inf')] * V for _ in range(V)]
    next_vertex = [[None] * V for _ in range(V)]
    
    # Initialize distances and next vertices
    for i in range(V):
        for j in range(V):
            if i == j:
                dist[i][j] = 0
            elif j in graph[i]:
                dist[i][j] = graph[i][j]
                next_vertex[i][j] = j
    
    # Main algorithm
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        next_vertex[i][j] = next_vertex[i][k]
    
    # Check for negative cycles
    for i in range(V):
        if dist[i][i] < 0:
            raise ValueError("Graph contains negative cycle")
    
    return dist, next_vertex

#include <vector>
#include <limits>
#include <stdexcept>

class FloydWarshall {
public:
    static pair<vector<vector<int>>, vector<vector<int>>> 
    FindAllPairsShortestPaths(const vector<vector<int>>& graph) {
        int V = graph.size();
        vector<vector<int>> dist(V, vector<int>(V));
        vector<vector<int>> next(V, vector<int>(V, -1));
        
        // Initialize distances and next vertices
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = graph[i][j];
                if (graph[i][j] != numeric_limits<int>::max() && i != j) {
                    next[i][j] = j;
                }
            }
        }
        
        // Main algorithm
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (dist[i][k] != numeric_limits<int>::max() && 
                        dist[k][j] != numeric_limits<int>::max() &&
                        dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        next[i][j] = next[i][k];
                    }
                }
            }
        }
        
        // Check for negative cycles
        for (int i = 0; i < V; i++) {
            if (dist[i][i] < 0) {
                throw runtime_error("Graph contains negative cycle");
            }
        }
        
        return {dist, next};
    }
};

public class FloydWarshall
{
    public static (int[,], int[,]) FindAllPairsShortestPaths(int[,] graph)
    {
        int V = graph.GetLength(0);
        int[,] dist = new int[V, V];
        int[,] next = new int[V, V];
        
        // Initialize distances and next vertices
        for (int i = 0; i < V; i++)
        {
            for (int j = 0; j < V; j++)
            {
                dist[i, j] = graph[i, j];
                next[i, j] = graph[i, j] != int.MaxValue && i != j ? j : -1;
            }
        }
        
        // Main algorithm
        for (int k = 0; k < V; k++)
        {
            for (int i = 0; i < V; i++)
            {
                for (int j = 0; j < V; j++)
                {
                    if (dist[i, k] != int.MaxValue && 
                        dist[k, j] != int.MaxValue &&
                        dist[i, j] > dist[i, k] + dist[k, j])
                    {
                        dist[i, j] = dist[i, k] + dist[k, j];
                        next[i, j] = next[i, k];
                    }
                }
            }
        }
        
        // Check for negative cycles
        for (int i = 0; i < V; i++)
        {
            if (dist[i, i] < 0)
            {
                throw new InvalidOperationException(
                    "Graph contains negative cycle");
            }
        }
        
        return (dist, next);
    }
    
    // Helper method to reconstruct path
    public static List<int> GetPath(int[,] next, int start, int end)
    {
        if (next[start, end] == -1)
            return new List<int>();
            
        var path = new List<int> { start };
        while (start != end)
        {
            start = next[start, end];
            path.Add(start);
        }
        
        return path;
    }
}

Complexity Analysis

Where V is the number of vertices in the graph. The algorithm always performs the same number of operations regardless of input.

Advantages and Disadvantages

Applications

• Network routing protocols
  • Finding optimal routes between all network nodes
  • Computing alternative paths for redundancy
• Traffic systems
  • Computing shortest routes between all locations
  • Planning public transportation networks
• Computer networks
  • Finding minimum latency paths
  • Network topology optimization
• Operations research
  • Solving all-pairs shortest path problems
  • Resource allocation optimization
• Graph analysis
  • Computing graph metrics
  • Finding graph diameter and center