🔮 Floyd-Warshall Fundamentals

🎯 What is the Floyd-Warshall Algorithm?

Floyd-Warshall is a classic dynamic programming algorithm that finds the shortest paths between all pairs of vertices in a weighted graph. It works for both directed and undirected graphs, handles negative edge weights (but not negative cycles), and is remarkably simple to implement — just three nested loops!

Time: O(V³) | Space: O(V²) | All-Pairs | Handles Negative Weights: ✅

Deep Explanation

Core Insight: The algorithm considers each vertex as a potential intermediate point on the shortest path between any two vertices. For each pair (i, j), we ask: "Is it better to go from i to j directly, or via vertex k?" By iterating k from 0 to V-1, we build up optimal paths using more and more intermediate vertices.

Key Intuition: At iteration k, dist[i][j] represents the shortest path from i to j using only vertices {0,1,...,k-1} as intermediates. When we incorporate vertex k, we update: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

📌 Dynamic Programming📌 All-Pairs Shortest Path📌 O(V³) Time📌 Simple Implementation

def floyd_warshall(graph):
    """
    graph: 2D list where graph[i][j] = weight from i to j
    Use float('inf') for no direct edge
    """
    V = len(graph)
    dist = [row[:] for row in graph]  # Deep copy
    
    for k in range(V):      # Intermediate vertex
        for i in range(V):  # Source vertex
            for j in range(V):  # Destination vertex
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

# Example usage
INF = float('inf')
graph = [
    [0, 3, INF, 5],
    [2, 0, INF, 4],
    [INF, 1, 0, INF],
    [INF, INF, 2, 0]
]
result = floyd_warshall(graph)
# result[i][j] = shortest distance from i to j

📐 Algorithm Walkthrough

🎯 Step-by-Step Example

Consider a graph with 4 vertices (0,1,2,3). Initial distances matrix:

k=0: Check paths through vertex 0. Update 2→1? 2→0(INF) skip. Update 3→2? 3→0(INF) skip.
k=1: Check paths through vertex 1. Update 0→3? 0→1(3)+1→3(4)=7 > current 5 → no. Update 2→3? 2→1(1)+1→3(4)=5 → update.
k=2: Check paths through vertex 2. Update 0→1? 0→2(INF) skip. Update 3→1? 3→2(2)+2→1(1)=3 → update.
k=3: Check paths through vertex 3. Various updates may occur.

The Three Nested Loops

The order of loops is crucial: k (intermediate) must be the outermost loop. This ensures that when we consider vertex k as an intermediate, we already have optimal paths using vertices 0..k-1 as intermediates. This builds up the solution incrementally.

⏱️ Time & Space Complexity

🎯 Complexity Analysis

Time Complexity: O(V³) — three nested loops, each iterating V times.
Space Complexity: O(V²) — stores the distance matrix.
Comparison: For dense graphs (E ≈ V²), Floyd-Warshall is optimal among all-pairs algorithms. For sparse graphs, running Dijkstra V times (O(V² log V + VE)) may be better.
V = 1000: ~1 billion operations (may be slow). V = 500: ~125 million operations (acceptable).

📊 Dynamic Programming Formulation

🎯 Recurrence Relation

Let dist^{(k)}[i][j] = shortest path from i to j using vertices {0,1,...,k-1} as intermediates.

Base Case (k=0): dist^{(0)}[i][j] = weight(i,j) (0 if i=j, INF if no direct edge)
Recurrence: dist^{(k+1)}[i][j] = min(dist^{(k)}[i][j], dist^{(k)}[i][k] + dist^{(k)}[k][j])
Final Answer: dist^{(V)}[i][j] = shortest path using all vertices as intermediates

Optimal Substructure

The recurrence exhibits optimal substructure: an optimal path either doesn't use vertex k as an intermediate, or consists of an optimal path from i to k followed by an optimal path from k to j.

💻 Multiple Implementations

# 1. In-place modification (most memory efficient)
def floyd_warshall_inplace(dist):
    V = len(dist)
    for k in range(V):
        for i in range(V):
            if dist[i][k] == float('inf'): continue
            dik = dist[i][k]
            for j in range(V):
                if dist[k][j] != float('inf'):
                    new_dist = dik + dist[k][j]
                    if new_dist < dist[i][j]:
                        dist[i][j] = new_dist
    return dist

# 2. With early termination for unreachable paths
def floyd_warshall_optimized(graph):
    V = len(graph)
    dist = [row[:] for row in graph]
    
    for k in range(V):
        for i in range(V):
            if dist[i][k] == float('inf'):
                continue
            for j in range(V):
                if dist[k][j] != float('inf'):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

# 3. For undirected graphs (symmetric adjacency)
def floyd_warshall_undirected(graph):
    V = len(graph)
    dist = [row[:] for row in graph]
    # Ensure symmetry (though input should already be symmetric)
    for i in range(V):
        for j in range(V):
            if dist[i][j] != dist[j][i]:
                dist[j][i] = dist[i][j] = min(dist[i][j], dist[j][i])
    return floyd_warshall(dist)

🛤️ Path Reconstruction

🎯 Reconstructing Shortest Paths

To reconstruct the actual shortest paths (not just distances), maintain a next matrix where next[i][j] stores the first vertex after i on the shortest path from i to j.

def floyd_warshall_with_path(graph):
    V = len(graph)
    dist = [row[:] for row in graph]
    next_node = [[None if row[j] == float('inf') else j for j in range(V)] for row in graph]
    
    for i in range(V):
        next_node[i][i] = i
    
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next_node[i][j] = next_node[i][k]  # Path: i -> ... -> k -> ... -> j
    
    def get_path(i, j):
        if next_node[i][j] is None:
            return None
        path = [i]
        while i != j:
            i = next_node[i][j]
            path.append(i)
        return path
    
    return dist, get_path

⚠️ Negative Weights & Cycles

🎯 Handling Negative Edges

Floyd-Warshall handles negative edge weights correctly. However, if a negative cycle exists (a cycle with total negative weight), shortest paths are undefined (can be arbitrarily negative). The algorithm can detect negative cycles by checking if dist[i][i] < 0 after completion — indicating a negative cycle reachable from i.

def floyd_warshall_negative_cycle_detection(graph):
    V = len(graph)
    dist = [row[:] for row in graph]
    
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    # Check for negative cycles
    for i in range(V):
        if dist[i][i] < 0:
            return None, True  # Negative cycle detected
    
    return dist, False

📊 Step-by-Step Visualization

🎯 Graph with 4 vertices

Initial distance matrix:

0→1: 3, 0→3: 5
1→0: 2, 1→3: 4
2→1: 1
3→2: 2

After k=0: No changes (no paths through vertex 0 improve existing paths)

After k=1: 2→3 improves: 2→1(1)+1→3(4)=5 (was INF). 0→3: 0→1(3)+1→3(4)=7 >5 (no change)

After k=2: 3→1: 3→2(2)+2→1(1)=3 (was INF). 3→3: 3→2(2)+2→1(1)+1→3(4)=7 → negative? No.

After k=3: Check paths through 3: 0→2: 0→3(5)+3→2(2)=7 (was INF). 1→2: 1→3(4)+3→2(2)=6 (was INF).

✅ Correctness Proof & Invariants

🎯 Proof by Induction

Invariant: After the k-th iteration of the outer loop, dist[i][j] contains the shortest path from i to j using only vertices {0,1,...,k-1} as intermediate vertices.

Base case (k=0): No intermediate vertices allowed, so dist[i][j] = direct edge weight (or INF).

Inductive step: When considering vertex k, the shortest path from i to j either includes k as an intermediate or it doesn't. If it includes k, then the optimal path is optimal(i→k) + optimal(k→j), which we have from previous iterations. The min of these two options gives the optimal path using vertices up to k.

📈 Comparison with Other AP Algorithms

vs V × Dijkstra: O(V² log V + VE) with binary heap, O(V³) with array. Better for sparse graphs.
vs V × Bellman-Ford: O(V²E) — much slower than Floyd-Warshall for dense graphs.
vs Johnson's Algorithm: O(VE log V) — reweights edges to make all weights non-negative, then runs Dijkstra V times. Best for sparse graphs with negative edges.
When to use Floyd-Warshall: Dense graphs, small V (≤500), simple implementation needed, or transitive closure problems.

⚡ Optimizations & Variants

Min-Plus Matrix Multiplication: Floyd-Warshall is essentially repeated min-plus multiplication.
Blocked/Parallel Floyd-Warshall: Partition matrix into blocks for better cache locality and parallel execution.
Space Optimization: For path reconstruction, store only next pointers (O(V²) space).
Transitive Closure (Unweighted): Use Boolean OR/AND instead of min/plus — O(V³) but can be optimized with bitsets to O(V³/wordsize).

🌍 Real-World Applications

Network Routing: Computing all-pairs shortest paths for routing tables in small networks.
Graph Analytics: Computing graph diameter, eccentricity, closeness centrality.
Transitive Closure: Determining reachability in directed graphs (e.g., dependency resolution).
Minimum Cost Path in Grids: With obstacles and varying costs.
Database Query Optimization: Join order optimization in some database systems.
Social Network Analysis: Computing degrees of separation between all users.

🔗 Transitive Closure

🎯 Reachability in Graphs

Transitive closure determines if there exists a path from vertex i to vertex j. Floyd-Warshall can be adapted using Boolean logic: reach[i][j] = reach[i][j] OR (reach[i][k] AND reach[k][j]). This is useful for reachability analysis, parsing grammars (CYK algorithm), and dependency graphs.

def transitive_closure(graph):
    """
    graph: adjacency matrix (True = edge exists)
    Returns reachability matrix
    """
    V = len(graph)
    reach = [row[:] for row in graph]
    
    for i in range(V):
        reach[i][i] = True
    
    for k in range(V):
        for i in range(V):
            if reach[i][k]:
                for j in range(V):
                    if reach[k][j]:
                        reach[i][j] = True
    return reach

# With bitset optimization (faster)
def transitive_closure_bitset(adj):
    V = len(adj)
    reach = [row[:] for row in adj]
    for i in range(V):
        reach[i][i] = 1
    for k in range(V):
        for i in range(V):
            if reach[i][k]:
                # OR the entire row at once
                for j in range(V):
                    reach[i][j] |= reach[k][j]
    return reach

💪 Practice & Problem Patterns

🎯 Classic Floyd-Warshall Problems

Find the City With Smallest Number of Neighbors (LeetCode 1334): Use Floyd-Warshall to compute all-pairs distances, then count reachable cities within threshold.
Detect Negative Cycles (GFG): Standard cycle detection after Floyd-Warshall.
Shortest Path in a Grid with obstacles and weights: Convert grid to graph, run Floyd-Warshall.
Course Schedule IV (LeetCode 1462): Transitive closure to determine prerequisites.
Minimum Cost to Connect All Nodes: After computing all-pairs shortest paths, MST becomes easier.
Cheapest Flights Within K Stops (variant): While usually Bellman-Ford, can be solved with Floyd-Warshall by storing hops information.

# LeetCode 1334 - Find the City With Smallest Number of Neighbors
def findTheCity(n, edges, distanceThreshold):
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
        dist[v][u] = w
    
    # Floyd-Warshall
    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]
    
    # Count reachable cities within threshold
    best_city = -1
    min_count = n
    for i in range(n):
        count = sum(1 for j in range(n) if i != j and dist[i][j] <= distanceThreshold)
        if count <= min_count:
            min_count = count
            best_city = i
    return best_city