Floyd-Warshall algorithm

Introduction

The Floyd-Warshall algorithm is a dynamic programming technique used to find the shortest paths between all pairs of vertices in a weighted graph. Unlike algorithms that find shortest paths from a single source (like Dijkstra's), Floyd-Warshall computes the shortest distance between every pair of nodes simultaneously.

Key Characteristics:

• Works with both positive and negative edge weights (but no negative cycles)

• Time complexity: O(V³) where V is the number of vertices

• Space complexity: O(V²)

• Uses dynamic programming with a bottom-up approach

Edge weight = the "cost" of traveling along that connection (distance, time, money, etc.)

A cycle is a path that starts and ends at the same node, going through other nodes.

Formula

The core recurrence relation is:

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

Where:

• dist[i][j][k] = shortest distance from vertex i to vertex j using vertices {0, 1, ..., k} as intermediate nodes

• i = source vertex

• j = destination vertex

• k = intermediate vertex being considered

Simplified 2D version:

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

Initialisation:

• dist[i][j] = weight(i,j) if there's a direct edge

• dist[i][j] = ∞ if no direct edge exists

• dist[i][i] = 0 for all vertices

Usage

When to Use Floyd-Warshall

• All-pairs shortest paths: Need distances between every pair of vertices

• Small to medium graphs: Due to O(V³) complexity

• Negative weights allowed: Unlike Dijkstra's algorithm

• Dense graphs: More efficient than running Dijkstra V times

• Transitive closure: Finding reachability between all vertex pairs

Common Applications

• Network routing protocols: Finding optimal paths in communication networks

• Game pathfinding: Precomputing distances in game maps

• Social network analysis: Finding degrees of separation

• Urban planning: Analysing transportation networks

• Arbitrage detection: Finding negative cycles in financial markets

Algorithm Steps

1. Initialise distance matrix with direct edge weights

2. For each intermediate vertex k (0 to V-1):

   • For each source vertex i (0 to V-1):

     • For each destination vertex j (0 to V-1):

       • Update dist[i][j] if path through k is shorter

3. Result: dist[i][j] contains shortest distance from i to j

Example

A --3-- B
|       |
2       1  
|       |
C --4-- D

Initial matrix

     A  B  C  D
A  [ 0  3  2  ∞ ]
B  [ ∞  0  ∞  1 ]  
C  [ ∞  ∞  0  4 ]
D  [ ∞  ∞  ∞  0 ]

After running the algorithm

     A  B  C  D
A  [ 0  3  2  6 ]  ← A to D: A→C→D (2+4=6)
B  [ ∞  0  ∞  1 ]
C  [ ∞  ∞  0  4 ]  
D  [ ∞  ∞  ∞  0 ]