Floyd-Warshall Algorithm - All Pairs Shortest Path

Find shortest paths between all pairs of vertices in a weighted graph using dynamic programming

Language Selection

Choose your preferred programming language

Showing: Python

Floyd-Warshall Algorithm - All Pairs Shortest Path

Problem Statement

Given a weighted directed graph, find the shortest distances between every pair of vertices. The graph may contain negative weight edges but no negative weight cycles.

The Floyd-Warshall algorithm is a dynamic programming approach that computes shortest paths between all pairs of vertices in O(V³) time.

Input/Output Specifications

Input: A weighted directed graph represented as:
- n vertices (numbered 0 to n-1)
- Adjacency matrix graph[i][j] representing edge weight from vertex i to j
- graph[i][j] = INF if no direct edge exists
- graph[i][i] = 0 for all vertices
Output: Matrix of shortest distances between all pairs of vertices

Constraints

1 <= n <= 200
-10^4 <= graph[i][j] <= 10^4
No negative weight cycles
graph[i][i] = 0

Examples

Example 1:

Input: graph = [
  [0, 3, INF, 5],
  [2, 0, INF, 4],
  [INF, 1, 0, INF],
  [INF, INF, 2, 0]
]
Output: [
  [0, 3, 7, 5],
  [2, 0, 6, 4],
  [3, 1, 0, 5],
  [5, 3, 2, 0]
]
Explanation: Shortest paths computed using intermediate vertices

Example 2:

Input: graph = [
  [0, 1, 4],
  [INF, 0, 2],
  [INF, INF, 0]
]
Output: [
  [0, 1, 3],
  [INF, 0, 2],
  [INF, INF, 0]
]
Explanation: No path from vertex 1 or 2 to vertex 0

Example 3:

Input: graph = [
  [0, -1, 4],
  [INF, 0, 3],
  [INF, INF, 0]
]
Output: [
  [0, -1, 2],
  [INF, 0, 3],
  [INF, INF, 0]
]
Explanation: Negative edge weights handled correctly

Solution Approaches

Approach 1: Standard Floyd-Warshall Algorithm (Optimal)

Algorithm Explanation:

Initialize distance matrix with direct edge weights
For each intermediate vertex k (0 to n-1):
- For each source vertex i (0 to n-1):
  - For each destination vertex j (0 to n-1):
    - If path through k is shorter, update distance[i][j]
The triple nested loop considers all possible intermediate vertices

Implementation:

Python:

def floyd_warshall(graph):
    """
    Find all pairs shortest paths using Floyd-Warshall
    Time: O(V^3)
    Space: O(V^2)
    """
    n = len(graph)
    INF = float('inf')
    
    # Initialize distance matrix with input graph
    dist = [[graph[i][j] for j in range(n)] for i in range(n)]
    
    # Floyd-Warshall algorithm
    for k in range(n):  # Intermediate vertex
        for i in range(n):  # Source vertex
            for j in range(n):  # Destination vertex
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

def floyd_warshall_with_path(graph):
    """
    Floyd-Warshall with path reconstruction
    Time: O(V^3)
    Space: O(V^2)
    """
    n = len(graph)
    INF = float('inf')
    
    # Initialize distance and next matrices
    dist = [[graph[i][j] for j in range(n)] for i in range(n)]
    next_vertex = [[j if graph[i][j] != INF else -1 for j in range(n)] 
                   for i in range(n)]
    
    # Set diagonal to point to self
    for i in range(n):
        next_vertex[i][i] = i
    
    # Floyd-Warshall with path tracking
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if (dist[i][k] != INF and dist[k][j] != INF and 
                    dist[i][k] + dist[k][j] < dist[i][j]):
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next_vertex[i][j] = next_vertex[i][k]
    
    return dist, next_vertex

def get_path(next_vertex, start, end):
    """Reconstruct path from start to end"""
    if next_vertex[start][end] == -1:
        return []
    
    path = [start]
    current = start
    while current != end:
        current = next_vertex[current][end]
        path.append(current)
    
    return path

Java:

class Solution {
    /**
     * Find all pairs shortest paths using Floyd-Warshall
     * Time: O(V^3)
     * Space: O(V^2)
     */
    public int[][] floydWarshall(int[][] graph) {
        int n = graph.length;
        int INF = Integer.MAX_VALUE;
        
        // Initialize distance matrix
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = graph[i][j];
            }
        }
        
        // Floyd-Warshall algorithm
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != INF && dist[k][j] != INF) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
        
        return dist;
    }
    
    /**
     * Floyd-Warshall with path reconstruction
     */
    public class FloydWarshallResult {
        public int[][] distances;
        public int[][] next;
        
        public FloydWarshallResult(int[][] distances, int[][] next) {
            this.distances = distances;
            this.next = next;
        }
    }
    
    public FloydWarshallResult floydWarshallWithPath(int[][] graph) {
        int n = graph.length;
        int INF = Integer.MAX_VALUE;
        
        int[][] dist = new int[n][n];
        int[][] next = new int[n][n];
        
        // Initialize matrices
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = graph[i][j];
                if (graph[i][j] != INF) {
                    next[i][j] = j;
                } else {
                    next[i][j] = -1;
                }
            }
            next[i][i] = i;
        }
        
        // Floyd-Warshall with path tracking
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; 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];
                        next[i][j] = next[i][k];
                    }
                }
            }
        }
        
        return new FloydWarshallResult(dist, next);
    }
    
    public List<Integer> getPath(int[][] next, int start, int end) {
        if (next[start][end] == -1) {
            return new ArrayList<>();
        }
        
        List<Integer> path = new ArrayList<>();
        path.add(start);
        int current = start;
        
        while (current != end) {
            current = next[current][end];
            path.add(current);
        }
        
        return path;
    }
}

Go:

// floydWarshall - Find all pairs shortest paths
// Time: O(V^3)
// Space: O(V^2)
func floydWarshall(graph [][]int) [][]int {
    n := len(graph)
    INF := math.MaxInt32
    
    // Initialize distance matrix
    dist := make([][]int, n)
    for i := 0; i < n; i++ {
        dist[i] = make([]int, n)
        copy(dist[i], graph[i])
    }
    
    // Floyd-Warshall algorithm
    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if dist[i][k] != INF && dist[k][j] != INF {
                    if dist[i][k]+dist[k][j] < dist[i][j] {
                        dist[i][j] = dist[i][k] + dist[k][j]
                    }
                }
            }
        }
    }
    
    return dist
}

type FloydWarshallResult struct {
    Distances [][]int
    Next      [][]int
}

// floydWarshallWithPath - Floyd-Warshall with path reconstruction
func floydWarshallWithPath(graph [][]int) FloydWarshallResult {
    n := len(graph)
    INF := math.MaxInt32
    
    // Initialize distance and next matrices
    dist := make([][]int, n)
    next := make([][]int, n)
    
    for i := 0; i < n; i++ {
        dist[i] = make([]int, n)
        next[i] = make([]int, n)
        
        for j := 0; j < n; j++ {
            dist[i][j] = graph[i][j]
            if graph[i][j] != INF {
                next[i][j] = j
            } else {
                next[i][j] = -1
            }
        }
        next[i][i] = i
    }
    
    // Floyd-Warshall with path tracking
    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if dist[i][k] != INF && dist[k][j] != INF {
                    newDist := dist[i][k] + dist[k][j]
                    if newDist < dist[i][j] {
                        dist[i][j] = newDist
                        next[i][j] = next[i][k]
                    }
                }
            }
        }
    }
    
    return FloydWarshallResult{dist, next}
}

func getPath(next [][]int, start, end int) []int {
    if next[start][end] == -1 {
        return []int{}
    }
    
    path := []int{start}
    current := start
    
    for current != end {
        current = next[current][end]
        path = append(path, current)
    }
    
    return path
}

JavaScript:

/**
 * Find all pairs shortest paths using Floyd-Warshall
 * Time: O(V^3)
 * Space: O(V^2)
 */
function floydWarshall(graph) {
    const n = graph.length;
    const INF = Infinity;
    
    // Initialize distance matrix
    const dist = graph.map(row => [...row]);
    
    // Floyd-Warshall algorithm
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (dist[i][k] !== INF && dist[k][j] !== INF) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    
    return dist;
}

/**
 * Floyd-Warshall with path reconstruction
 */
function floydWarshallWithPath(graph) {
    const n = graph.length;
    const INF = Infinity;
    
    // Initialize distance and next matrices
    const dist = graph.map(row => [...row]);
    const next = Array.from({length: n}, () => new Array(n));
    
    // Initialize next matrix
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (graph[i][j] !== INF) {
                next[i][j] = j;
            } else {
                next[i][j] = -1;
            }
        }
        next[i][i] = i;
    }
    
    // Floyd-Warshall with path tracking
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (dist[i][k] !== INF && dist[k][j] !== INF) {
                    const newDist = dist[i][k] + dist[k][j];
                    if (newDist < dist[i][j]) {
                        dist[i][j] = newDist;
                        next[i][j] = next[i][k];
                    }
                }
            }
        }
    }
    
    return { distances: dist, next: next };
}

function getPath(next, start, end) {
    if (next[start][end] === -1) {
        return [];
    }
    
    const path = [start];
    let current = start;
    
    while (current !== end) {
        current = next[current][end];
        path.push(current);
    }
    
    return path;
}

// Alternative implementation with space optimization
function floydWarshallOptimized(graph) {
    const n = graph.length;
    const dist = graph.map(row => [...row]);
    
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            if (dist[i][k] === Infinity) continue;
            for (let j = 0; j < n; j++) {
                if (dist[k][j] === Infinity) continue;
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    
    return dist;
}

C#:

public class Solution {
    /// <summary>
    /// Find all pairs shortest paths using Floyd-Warshall
    /// Time: O(V^3)
    /// Space: O(V^2)
    /// </summary>
    public int[,] FloydWarshall(int[,] graph) {
        int n = graph.GetLength(0);
        int INF = int.MaxValue;
        
        // Initialize distance matrix
        int[,] dist = new int[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i, j] = graph[i, j];
            }
        }
        
        // Floyd-Warshall algorithm
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i, k] != INF && dist[k, j] != INF) {
                        dist[i, j] = Math.Min(dist[i, j], dist[i, k] + dist[k, j]);
                    }
                }
            }
        }
        
        return dist;
    }
    
    /// <summary>
    /// Floyd-Warshall with path reconstruction
    /// </summary>
    public class FloydWarshallResult {
        public int[,] Distances { get; set; }
        public int[,] Next { get; set; }
        
        public FloydWarshallResult(int[,] distances, int[,] next) {
            Distances = distances;
            Next = next;
        }
    }
    
    public FloydWarshallResult FloydWarshallWithPath(int[,] graph) {
        int n = graph.GetLength(0);
        int INF = int.MaxValue;
        
        int[,] dist = new int[n, n];
        int[,] next = new int[n, n];
        
        // Initialize matrices
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i, j] = graph[i, j];
                if (graph[i, j] != INF) {
                    next[i, j] = j;
                } else {
                    next[i, j] = -1;
                }
            }
            next[i, i] = i;
        }
        
        // Floyd-Warshall with path tracking
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i, k] != INF && dist[k, j] != INF) {
                        long newDist = (long)dist[i, k] + dist[k, j];
                        if (newDist < dist[i, j]) {
                            dist[i, j] = (int)newDist;
                            next[i, j] = next[i, k];
                        }
                    }
                }
            }
        }
        
        return new FloydWarshallResult(dist, next);
    }
    
    public List<int> GetPath(int[,] next, int start, int end) {
        if (next[start, end] == -1) {
            return new List<int>();
        }
        
        var path = new List<int> { start };
        int current = start;
        
        while (current != end) {
            current = next[current, end];
            path.Add(current);
        }
        
        return path;
    }
    
    // LINQ-based alternative for cleaner syntax
    public int[,] FloydWarshallLinq(int[,] graph) {
        int n = graph.GetLength(0);
        var dist = (int[,])graph.Clone();
        
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i, k] != int.MaxValue && dist[k, j] != int.MaxValue) {
                        dist[i, j] = Math.Min(dist[i, j], dist[i, k] + dist[k, j]);
                    }
                }
            }
        }
        
        return dist;
    }
}

Approach 2: Space-Optimized Version

Algorithm Explanation: Since we only need the current state to compute the next state, we can optimize space by using a single matrix and updating it in-place.

Implementation Example (Python):

def floyd_warshall_space_optimized(graph):
    """
    Space-optimized Floyd-Warshall
    Time: O(V^3)
    Space: O(1) additional space
    """
    n = len(graph)
    
    # Work directly on the input matrix (or create a copy)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][k] != float('inf') and graph[k][j] != float('inf'):
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    
    return graph

Complexity Analysis:

Time Complexity: O(V³) - Three nested loops over all vertices
Space Complexity: O(V²) - For storing the distance matrix, O(1) additional space for space-optimized version

Trade-offs:

Standard Version: Preserves original graph, supports path reconstruction
Space-Optimized: Modifies input in-place, minimal memory usage

Key Insights

Dynamic Programming: Builds optimal solutions using previously computed subproblems
Intermediate Vertices: The key insight is considering all possible intermediate vertices
Optimal Substructure: Shortest path from i to j through k uses shortest paths from i to k and k to j
Negative Edges: Handles negative edge weights (but not negative cycles)

Edge Cases

No Path Exists: Distance remains infinity
Self-loops: Distance from vertex to itself is 0
Negative Edges: Algorithm handles them correctly
Disconnected Graph: Some distances remain infinity
Single Vertex: Trivial case with distance 0

How Solutions Handle Edge Cases:

No path: INF values preserved in final matrix
Self-loops: Diagonal initialized to 0
Negative edges: Min operation handles correctly
Disconnected components: INF distances indicate no path
Single vertex: Algorithm handles n=1 correctly

Test Cases

def test_floyd_warshall():
    INF = float('inf')
    
    # Basic test case
    graph1 = [
        [0, 3, INF, 5],
        [2, 0, INF, 4],
        [INF, 1, 0, INF],
        [INF, INF, 2, 0]
    ]
    result1 = floyd_warshall(graph1)
    expected1 = [
        [0, 3, 7, 5],
        [2, 0, 6, 4],
        [3, 1, 0, 5],
        [5, 3, 2, 0]
    ]
    assert result1 == expected1
    
    # Triangle with negative edge
    graph2 = [
        [0, -1, 4],
        [INF, 0, 3],
        [INF, INF, 0]
    ]
    result2 = floyd_warshall(graph2)
    expected2 = [
        [0, -1, 2],
        [INF, 0, 3],
        [INF, INF, 0]
    ]
    assert result2 == expected2
    
    # Disconnected graph
    graph3 = [
        [0, 1],
        [INF, 0]
    ]
    result3 = floyd_warshall(graph3)
    expected3 = [
        [0, 1],
        [INF, 0]
    ]
    assert result3 == expected3
    
    # Single vertex
    graph4 = [[0]]
    result4 = floyd_warshall(graph4)
    assert result4 == [[0]]
    
    print("All tests passed!")

test_floyd_warshall()

Follow-up Questions

Negative Cycle Detection: How would you detect negative weight cycles?
Transitive Closure: How to find if there’s a path between every pair of vertices?
Memory Optimization: Can you reduce space complexity for large sparse graphs?
Parallel Implementation: How would you parallelize the algorithm?
Online Version: Handle edge weight updates efficiently

Common Mistakes

Incorrect Loop Order: Wrong nesting of k, i, j loops
- Problem: Doesn’t consider all intermediate vertices properly
- Solution: k must be the outermost loop
Overflow Issues: Adding large numbers without checking
- Problem: Integer overflow with large weights
- Solution: Check for INF before addition
Wrong Initialization: Not handling unreachable vertices
- Problem: Incorrect distances for non-adjacent vertices
- Solution: Initialize with INF for non-edges
Negative Cycle Handling: Not detecting negative cycles
- Problem: Algorithm gives incorrect results with negative cycles
- Solution: Check diagonal elements after algorithm

Interview Tips

Algorithm Choice: Mention when Floyd-Warshall is preferred over Dijkstra
Space-Time Tradeoffs: Discuss memory usage vs computation time
Path Reconstruction: Be prepared to implement path tracking
Edge Cases: Always mention negative cycle detection
Applications: Understand real-world use cases (routing, game theory)

Concept Explanations

Dynamic Programming Approach: Floyd-Warshall uses the principle that the shortest path between two vertices either:

Goes directly between them, or
Goes through an intermediate vertex

All-Pairs vs Single-Source: While Dijkstra solves single-source shortest path, Floyd-Warshall solves all-pairs shortest path, making it suitable for dense graphs or when you need distances between all vertex pairs.

When to Apply: Use Floyd-Warshall for:

Small to medium-sized graphs (n ≤ 400)
Dense graphs where you need all-pairs distances
Graphs with negative edge weights (but no negative cycles)
Finding transitive closure of a relation