Floyd Warshall Algorithm: Explanation, Example, and Use Cases

The Floyd Warshall algorithm is a method to find the shortest paths between all pairs of points in a graph. It works by gradually improving the path estimates using intermediate points, and it handles graphs with positive or negative edge weights but no negative cycles.

How It Works

The Floyd Warshall algorithm finds the shortest path between every pair of points (nodes) in a graph by checking if going through an intermediate point can give a shorter path. Imagine you want to travel between cities, and you check if stopping at a third city makes your trip shorter than going directly.

It starts with the direct distances between points and then tries to improve these distances by considering each point as a possible stopover. This process repeats for all points, updating the shortest known paths step by step until no shorter path can be found.

This method uses a simple table (matrix) to keep track of distances and updates it in a way that ensures all shortest paths are found by the end.

Example

This example shows how the Floyd Warshall algorithm calculates shortest paths in a graph represented by a distance matrix. The matrix uses float('inf') to represent no direct path.

python

def floyd_warshall(graph):
    n = len(graph)
    dist = [row[:] for row in graph]  # Copy graph distances

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

# Example graph with 4 nodes
graph = [
    [0, 3, float('inf'), 7],
    [8, 0, 2, float('inf')],
    [5, float('inf'), 0, 1],
    [2, float('inf'), float('inf'), 0]
]

shortest_paths = floyd_warshall(graph)
for row in shortest_paths:
    print(row)

Output

[0, 3, 5, 6]
[7, 0, 2, 3]
[3, 6, 0, 1]
[2, 5, 7, 0]

When to Use

Use the Floyd Warshall algorithm when you need to find the shortest paths between all pairs of points in a graph, especially if the graph has negative edge weights but no negative cycles. It is useful in network routing, urban traffic planning, and analyzing social networks where you want to know the shortest connection between any two points.

It works best for smaller graphs because its time complexity grows quickly with the number of points. For very large graphs, other algorithms might be more efficient.

Key Points

• Finds shortest paths between all pairs of nodes in a graph.
• Works with positive and negative edge weights but no negative cycles.
• Uses a matrix updated iteratively considering intermediate nodes.
• Simple to implement but has cubic time complexity (O(n³)).
• Useful in routing, traffic, and network analysis.

Key Takeaways

Floyd Warshall finds shortest paths between all pairs of points in a graph.

It updates distances by considering each node as an intermediate stop.

It handles negative edges but not negative cycles.

Best for small to medium graphs due to O(n³) time complexity.

Commonly used in routing and network analysis tasks.