Floyd-Warshall Algorithm: Explained with Implementation in C and Python

The Floyd-Warshall Algorithm is a dynamic programming technique used to find the shortest paths between all pairs of vertices in a weighted graph. It works efficiently with both directed and undirected graphs and can handle positive and negative edge weights, as long as no negative-weight cycles exist in the graph.

In this detailed blog, we will explore the algorithm step by step, covering:

Introduction to the Floyd-Warshall Algorithm
Theoretical Foundation
Algorithm Explanation
Implementation in C and Python
Advantages and Limitations
Real-World Applications
Optimizations and Variations

Introduction to the Floyd-Warshall Algorithm

The Floyd-Warshall Algorithm is one of the most popular algorithms for solving the all-pairs shortest path problem. Given a graph $( G )$ with $( V )$ vertices and weighted edges, the algorithm calculates the shortest paths between every pair of vertices.

Unlike Dijkstra’s or Bellman-Ford algorithms that compute shortest paths from a single source vertex, Floyd-Warshall is designed for scenarios where all-pairs shortest paths are required.

Key Characteristics

Dynamic Programming Approach: The algorithm builds solutions incrementally using previously computed results.
Graph Representation: The graph is represented as an adjacency matrix.
Time Complexity: $( O(V^3) )$ , where $( V )$ is the number of vertices.
Space Complexity: $( O(V^2) )$ , for the adjacency matrix.

Theoretical Foundation

The Floyd-Warshall Algorithm relies on the concept of intermediate vertices. It determines the shortest path between two vertices $( u )$ and $( v )$ by considering whether to include a third vertex $( k )$ in the path.

Recursive Formula

For vertices $( u )$ , $( v )$ , and $( k )$ :

If $( k )$ is an intermediate vertex:
$[\text{dist}[u][v] = \min(\text{dist}[u][v], \text{dist}[u][k] + \text{dist}[k][v])]$
If $( k )$ is not included:
$[\text{dist}[u][v] = \text{dist}[u][v]]$

Initially:

$( \text{dist}[u][v] = \text{weight of edge from } u \text{ to } v )$ .
If no edge exists, $( \text{dist}[u][v] = \infty )$ .

Algorithm Explanation

The Floyd-Warshall Algorithm can be broken down into three main steps:

1. Initialization

Create a $( V \times V )$ distance matrix, where:

$( \text{dist}[i][j] = w_{ij} )$ (weight of the edge from $( i )$ to $( j ))$ .
If $( i = j )$ , set $( \text{dist}[i][j] = 0 )$ (distance to itself is zero).
If no edge exists between $( i )$ and $( j )$ , set $( \text{dist}[i][j] = \infty )$ .

2. Dynamic Programming Update

Iteratively update the distance matrix by considering each vertex as an intermediate vertex. For each pair of vertices $( u )$ $( v )$ , update:
$[\text{dist}[u][v] = \min(\text{dist}[u][v], \text{dist}[u][k] + \text{dist}[k][v])]$

3. Negative-Weight Cycle Detection

If $( \text{dist}[i][i] < 0 )$ for any vertex $( i )$ , the graph contains a negative-weight cycle.

Implementation in C

Here is a step-by-step C implementation of the Floyd-Warshall Algorithm:

C Code

#include <stdio.h>
#include <limits.h>

#define INF 99999
#define V 4

void printSolution(int dist[V][V]);

void floydWarshall(int graph[V][V]) {
    int dist[V][V];

    // Initialize the solution matrix same as input graph matrix
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    // Update dist[][] for all pairs using each vertex as intermediate
    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] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // Print the shortest distance matrix
    printSolution(dist);
}

void printSolution(int dist[V][V]) {
    printf("Shortest distances between every pair of vertices:\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF) {
                printf("%7s", "INF");
            } else {
                printf("%7d", dist[i][j]);
            }
        }
        printf("\n");
    }
}

int main() {
    int graph[V][V] = {
        {0, 5, INF, 10},
        {INF, 0, 3, INF},
        {INF, INF, 0, 1},
        {INF, INF, INF, 0}
    };

    floydWarshall(graph);
    return 0;
}

Explanation of C Code

Graph Representation: The graph is represented using an adjacency matrix. Edges with no direct connection are initialized as INF.
Distance Matrix Initialization: The dist matrix is initialized to match the graph initially.
Iterative Updates: Nested loops update the shortest path for all pairs of vertices using each vertex as an intermediate vertex.
Output: The final shortest path distances are printed in a tabular format.

Implementation in Python

Below is the Python implementation of the Floyd-Warshall Algorithm:

Python Code

INF = float('inf')

def floyd_warshall(graph):
    V = len(graph)
    dist = [row[:] for row in graph]  # Copy the graph to dist

    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    print_solution(dist)

def print_solution(dist):
    print("Shortest distances between every pair of vertices:")
    for row in dist:
        for value in row:
            print("INF" if value == float('inf') else value, end="\t")
        print()

# Example graph represented as an adjacency matrix
graph = [
    [0, 5, INF, 10],
    [INF, 0, 3, INF],
    [INF, INF, 0, 1],
    [INF, INF, INF, 0]
]

floyd_warshall(graph)

Explanation of Python Code

Graph Representation: The graph is an adjacency matrix where ( INF ) represents no direct connection.
Initialization: The dist matrix is initialized as a copy of the input graph.
Dynamic Updates: Triple nested loops update the dist matrix using the intermediate vertices.
Output: The shortest distances are displayed in a user-friendly format.

Advantages of Floyd-Warshall Algorithm

Handles Negative Weights: It works with graphs that contain negative edge weights (no negative cycles).
Simplicity: Easy to understand and implement compared to other all-pairs shortest path algorithms.
Versatility: Can handle dense graphs effectively.

Limitations of Floyd-Warshall Algorithm

Time Complexity:
The $( O(V^3) )$ time complexity makes it inefficient for graphs with a large number of vertices, especially when $( V )$ exceeds a few thousand.
Space Complexity:
The adjacency matrix requires $( O(V^2) )$ space, which can be a bottleneck for memory-constrained systems.
No Negative Cycles:
If a negative-weight cycle exists, the algorithm cannot compute valid shortest paths and may produce incorrect results.

Real-World Applications of Floyd-Warshall Algorithm

Despite its limitations, the Floyd-Warshall Algorithm is widely used in various real-world scenarios:

1. Routing in Networks

Use Case: Finding the shortest path in communication networks.
Example: In internet routing protocols, the algorithm helps in determining the least cost path for data packets between routers.

2. Flight Reservation Systems

Use Case: Determining the shortest travel distance or time between all pairs of cities.
Example: Online flight booking platforms calculate the shortest routes using algorithms like Floyd-Warshall.

3. Transitive Closure

Use Case: Finding whether a path exists between two vertices in a directed graph.
Example: In databases, it can be used to determine reachability in dependency graphs.

4. Game Development

Use Case: Navigation systems in games to calculate the shortest distance between various points in a virtual map.
Example: AI-controlled characters use Floyd-Warshall for pathfinding in complex terrains.

Negative Cycle Detection

One of the notable features of the Floyd-Warshall Algorithm is its ability to detect negative cycles. If $( \text{dist}[i][i] < 0 )$ for any vertex $( i )$ , the graph contains a negative-weight cycle. This is because a negative distance to itself implies a cycle with a net negative weight.

Implementation for Negative Cycle Detection

In both C and Python implementations, the condition can be checked after the main iterations:

C Code Addition

for (int i = 0; i < V; i++) {
    if (dist[i][i] < 0) {
        printf("Graph contains a negative weight cycle.\n");
        return;
    }
}

Python Code Addition

for i in range(len(dist)):
    if dist[i][i] < 0:
        print("Graph contains a negative weight cycle.")
        return

Comparison with Other Algorithms

Floyd-Warshall vs Dijkstra

Feature	Floyd-Warshall	Dijkstra
Purpose	All-pairs shortest path	Single-source shortest path
Time Complexity	$( O(V^3) )$	$( O(V^2) )$ or $( O(E + V \log V) )$ with a priority queue
Graph Type	Handles negative weights	No negative weights allowed
Efficiency for Sparse Graphs	Inefficient	More efficient

Floyd-Warshall vs Bellman-Ford

Optimizations for Floyd-Warshall

1. Sparse Graph Optimization

If the graph is sparse (contains very few edges compared to vertices), algorithms like Dijkstra’s or Johnson’s Algorithm may be more efficient.

2. Memory Optimization

Instead of maintaining a full $( V \times V )$ matrix, two smaller matrices can be alternated to reduce memory usage.

3. Parallel Computing

Since updates to $( \text{dist}[u][v] )$ for each pair are independent, the algorithm can be parallelized to improve performance on large graphs.

Edge Cases to Consider

Graph with No Edges:

The distance between any two distinct vertices remains $( \infty )$ .

Disconnected Graph:

The algorithm gracefully handles disconnected graphs by retaining $( \infty )$ for unreachable pairs.

Graph with Negative Cycles:

Detection of negative cycles ensures correctness. If one exists, the algorithm cannot produce valid shortest paths.

Practical Example

Let’s consider a practical example to better understand the Floyd-Warshall Algorithm.

Input Graph (Adjacency Matrix)

      0   5   INF 10
      INF 0   3   INF
      INF INF 0   1
      INF INF INF 0

Step-by-Step Execution

Initialization

      0   5   INF 10
      INF 0   3   INF
      INF INF 0   1
      INF INF INF 0

After First Iteration (k=0)

      0   5   INF 10
      INF 0   3   INF
      INF INF 0   1
      INF INF INF 0

After Second Iteration (k=1)

      0   5    8   INF
      INF 0    3   INF
      INF INF  0    1
      INF INF INF   0

After Third Iteration (k=2)

      0   5    8    9
      INF 0    3    4
      INF INF  0    1
      INF INF INF   0

Final Result

      0   5    8    9
      INF 0    3    4
      INF INF  0    1
      INF INF INF   0

The Floyd-Warshall Algorithm is a fundamental graph algorithm that provides a comprehensive solution to the all-pairs shortest path problem. While its ( O(V^3) ) complexity may limit its use in extremely large graphs, it remains highly relevant for dense graphs and applications requiring negative-weight edge handling.

This blog covered the theoretical foundation, step-by-step explanation, implementation in C and Python, real-world applications, optimizations, and a comparison with other algorithms. By understanding Floyd-Warshall, developers gain a powerful tool for solving complex graph problems.

If you found this blog useful, share it with fellow developers and students preparing for interviews or working on graph-related projects. For more such algorithm tutorials, subscribe to our newsletter and stay updated with the latest in programming!

Feature	Floyd-Warshall	Bellman-Ford
Purpose	All-pairs shortest path	Single-source shortest path
Time Complexity	$( O(V^3) )$	$( O(V \cdot E) )$
Handles Negative Cycles	Detects them	Detects them
Efficiency for Dense Graphs	Efficient	Less efficient