Mastering Algorithms

Floyd-Warshall Algorithm

Overview

The Floyd-Warshall algorithm is a dynamic programming algorithm for finding shortest paths between all pairs of vertices in a weighted graph. It works on both directed and undirected graphs, and can handle negative edge weights (but not negative cycles).

Unlike Dijkstra's and Bellman-Ford which find shortest paths from a single source, Floyd-Warshall finds shortest paths between every pair of vertices in one execution. It uses a dynamic programming approach, building up solutions by considering intermediate vertices.

The algorithm is particularly useful when you need shortest paths between all pairs of vertices, such as in network analysis, social network analysis, and transportation planning.

How It Works

The algorithm uses dynamic programming with the following recurrence relation:

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

For each intermediate vertex k, it checks if going through k gives a shorter path from i to j.

  1. Initialize: Create distance matrix with direct edge weights
  2. Iterate: For each vertex k (0 to V-1):
    • For each pair (i, j), check if path i → k → j is shorter
    • Update dist[i][j] if shorter path found
  3. Result: Distance matrix contains shortest paths between all pairs

Floyd-Warshall Algorithm Pseudocode


FloydWarshall(graph):
    n = number of vertices
    dist = n × n matrix initialized with:
        dist[i][j] = weight(i, j) if edge exists
        dist[i][j] = ∞ if no edge
        dist[i][i] = 0
    
    for k = 0 to n-1:
        for i = 0 to n-1:
            for j = 0 to n-1:
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

Implementation


def floyd_warshall(graph):
    """
    graph: adjacency matrix (n × n)
           graph[i][j] = weight if edge exists, ∞ if no edge, 0 if i == j
    Returns: distance matrix with shortest paths between all pairs
    """
    n = len(graph)
    dist = [row[:] for row in graph]  # Copy graph
    
    # Floyd-Warshall algorithm
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

def floyd_warshall_with_paths(graph):
    """Floyd-Warshall with path reconstruction"""
    n = len(graph)
    dist = [row[:] for row in graph]
    next_vertex = [[None] * n for _ in range(n)]
    
    # Initialize next matrix
    for i in range(n):
        for j in range(n):
            if graph[i][j] != float('inf'):
                next_vertex[i][j] = j
    
    # Floyd-Warshall
    for k in range(n):
        for i in range(n):
            for j in range(n):
                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]
    
    return dist, next_vertex

def reconstruct_path(next_vertex, start, end):
    """Reconstruct path from next matrix"""
    if next_vertex[start][end] is None:
        return []
    
    path = [start]
    while start != end:
        start = next_vertex[start][end]
        path.append(start)
    return path

Complexity Analysis

  • Time Complexity: O(V³) - three nested loops over all vertices
  • Space Complexity: O(V²) - for distance matrix

The algorithm is simple and easy to implement, but the cubic time complexity makes it suitable only for small to medium-sized graphs (typically V < 500).

Detecting Negative Cycles

After running Floyd-Warshall, check for negative cycles by looking for negative values on the diagonal of the distance matrix. If dist[i][i] < 0 for any vertex i, there's a negative cycle. 


def has_negative_cycle(dist):
    """Check if graph has negative cycle"""
    n = len(dist)
    for i in range(n):
        if dist[i][i] < 0:
            return True
    return False

Example

Finding shortest paths between all pairs: 

Graph:
    0 --4--> 1
    |        |
    1        2
    |        |
    v        v
    2 --3--> 3

Initial distance matrix:
    0   1   2   3
0   0   4   ∞   ∞
1   ∞   0   2   ∞
2   1   ∞   0   3
3   ∞   ∞   ∞   0

After k=0 (considering vertex 0 as intermediate):
    0   1   2   3
0   0   4   ∞   ∞
1   ∞   0   2   ∞
2   1   5   0   3
3   ∞   ∞   ∞   0

After k=1 (considering vertex 1 as intermediate):
    0   1   2   3
0   0   4   6   ∞
1   ∞   0   2   ∞
2   1   5   0   3
3   ∞   ∞   ∞   0

After k=2 (considering vertex 2 as intermediate):
    0   1   2   3
0   0   4   6   9
1   3   0   2   5
2   1   5   0   3
3   ∞   ∞   ∞   0

After k=3 (considering vertex 3 as intermediate):
    (no changes)

Final result: All-pairs shortest paths

When to Use Floyd-Warshall

Floyd-Warshall is ideal when:

  • You need shortest paths between all pairs of vertices
  • Graph is small to medium (V < 500)
  • Graph can have negative weights (but not negative cycles)
  • You need a simple, easy-to-implement solution
  • Dense graphs where most pairs are connected

Consider alternatives when:

  • Graph is very large → Use multiple Dijkstra/Bellman-Ford calls
  • Only need single-source shortest paths → Use Dijkstra's or Bellman-Ford
  • Sparse graph → Dijkstra/Bellman-Ford may be more efficient

Floyd-Warshall vs Other Algorithms

Algorithm Pairs Time Complexity Best For
Dijkstra's Single source O((V + E) log V) Non-negative weights
Bellman-Ford Single source O(V × E) Negative weights
Floyd-Warshall All pairs O(V³) All-pairs, small graphs

Real-World Applications

  • Network Analysis: Finding shortest paths in computer networks
  • Social Networks: Computing distances between all users
  • Transportation: Finding shortest routes between all cities
  • Game Development: Precomputing distances for pathfinding
  • Clustering: Computing distance matrices for clustering algorithms

Related Algorithms

Explore other searching algorithms: