Floyd-Warshall Algorithm - The All-Pairs Master

"Khi cần biết khoảng cách từ MỌI đỉnh đến MỌI đỉnh khác, Floyd-Warshall là câu trả lời." - HPN

Problem Statement

Single-Source Shortest Path (Dijkstra, Bellman-Ford): Tìm shortest path từ 1 nguồn đến tất cả đích.

All-Pairs Shortest Path: Tìm shortest path từ MỌI đỉnh đến MỌI đỉnh khác.

📘 Tại sao cần Floyd-Warshall?

Có thể chạy Dijkstra V lần → $O (V \times E \log V)$

Với dense graph (E ≈ V²): $O (V^{3} \log V)$

Floyd-Warshall: $O (V^{3})$ - Đơn giản hơn và thường nhanh hơn cho dense graph!

When to Use

Scenario	Best Choice	Why
Sparse graph (E << V²)	Dijkstra × V	O(VE log V) < O(V³)
Dense graph (E ≈ V²)	Floyd-Warshall	Simpler, same complexity
Negative weights	Floyd-Warshall	Dijkstra fails
Need all pairs + negative cycle	Floyd-Warshall	Built-in detection
Connectivity matrix needed	Floyd-Warshall	Perfect fit

Real-World Applications

Domain	Use Case	Chi tiết
Networking	Routing tables	Tính đường đi ngắn nhất giữa mọi router
Social Networks	Degrees of separation	"6 degrees of Kevin Bacon"
Transportation	Flight connections	Min hops giữa mọi cặp sân bay
Game AI	Pathfinding cache	Precompute distances cho NPC movement
Database	Transitive closure	Kiểm tra reachability trong dependency graph

Core Concept: Dynamic Programming

Floyd-Warshall là DP trên đồ thị:

dp[k][i][j] = Shortest path i → j chỉ dùng vertices {0, 1, ..., k} làm intermediate

Transition:
dp[k][i][j] = min(
    dp[k-1][i][j],           # Không đi qua k
    dp[k-1][i][k] + dp[k-1][k][j]  # Đi qua k
)

Key Insight: Có thể tối ưu xuống 2D vì dp[k] chỉ phụ thuộc dp[k-1].

2D Matrix Visualization

Initial Graph (Adjacency Matrix):
     0    1    2    3
  ┌─────────────────────┐
0 │ 0    3    ∞    7   │
1 │ 8    0    2    ∞   │
2 │ 5    ∞    0    1   │
3 │ 2    ∞    ∞    0   │
  └─────────────────────┘

After k=0 (considering path through vertex 0):
     0    1    2    3
  ┌─────────────────────┐
0 │ 0    3    ∞    7   │
1 │ 8    0    2    15  │  ← 1→0→3 = 8+7 = 15 < ∞
2 │ 5    8    0    1   │  ← 2→0→1 = 5+3 = 8 < ∞
3 │ 2    5    ∞    0   │  ← 3→0→1 = 2+3 = 5 < ∞
  └─────────────────────┘

... After k=3 (Final):
     0    1    2    3
  ┌─────────────────────┐
0 │ 0    3    5    6   │
1 │ 5    0    2    3   │
2 │ 3    6    0    1   │
3 │ 2    5    7    0   │
  └─────────────────────┘

Implementation

Basic Floyd-Warshall

python

from typing import List, Tuple, Optional


def floyd_warshall(graph: List[List[float]]) -> List[List[float]]:
    """
    Floyd-Warshall Algorithm - Basic version.
    
    Args:
        graph: Adjacency matrix. graph[i][j] = weight(i→j), inf if no edge
    
    Returns:
        Distance matrix. dist[i][j] = shortest path i → j
    
    Time: O(V³)
    Space: O(V²)
    """
    V = len(graph)
    INF = float('inf')
    
    # Copy graph to dist matrix
    dist = [[graph[i][j] for j in range(V)] for i in range(V)]
    
    # DP: Try each vertex as intermediate
    for k in range(V):
        for i in range(V):
            for j in range(V):
                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

With Negative Cycle Detection

python

def floyd_warshall_with_cycle_detection(
    graph: List[List[float]]
) -> Tuple[List[List[float]], bool]:
    """
    Floyd-Warshall with negative cycle detection.
    
    Returns:
        (dist_matrix, has_negative_cycle)
    
    Negative cycle detection: If dist[i][i] < 0 for any i → negative cycle exists!
    """
    V = len(graph)
    INF = float('inf')
    
    dist = [[graph[i][j] for j in range(V)] for i in range(V)]
    
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    # Check diagonal for negative cycle
    has_negative_cycle = any(dist[i][i] < 0 for i in range(V))
    
    return dist, has_negative_cycle

With Path Reconstruction

python

def floyd_warshall_with_path(
    graph: List[List[float]]
) -> Tuple[List[List[float]], List[List[int]]]:
    """
    Floyd-Warshall with path reconstruction.
    
    Returns:
        (dist_matrix, next_matrix)
        next[i][j] = next vertex on shortest path from i to j
    """
    V = len(graph)
    INF = float('inf')
    
    dist = [[graph[i][j] for j in range(V)] for i in range(V)]
    next_vertex = [[-1] * V for _ in range(V)]
    
    # Initialize next matrix
    for i in range(V):
        for j in range(V):
            if graph[i][j] != INF and i != j:
                next_vertex[i][j] = j
    
    # Floyd-Warshall
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] != INF and dist[k][j] != INF:
                    if 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 reconstruct_path(next_matrix: List[List[int]], start: int, end: int) -> Optional[List[int]]:
    """Reconstruct path from start to end."""
    if next_matrix[start][end] == -1:
        return None
    
    path = [start]
    current = start
    
    while current != end:
        current = next_matrix[current][end]
        if current == -1:
            return None
        path.append(current)
    
    return path

Production Code

python

# HPN Engineering Standard
# Implementation: Floyd-Warshall - Full Featured

from typing import List, Tuple, Optional, Set
from dataclasses import dataclass
from enum import Enum


class ReachabilityType(Enum):
    UNREACHABLE = 0
    REACHABLE = 1
    NEGATIVE_INFINITY = -1  # Reachable through negative cycle


@dataclass
class FloydWarshallResult:
    dist: List[List[float]]
    next_vertex: List[List[int]]
    has_negative_cycle: bool
    affected_by_cycle: List[List[bool]]


class FloydWarshall:
    """
    Production-ready Floyd-Warshall implementation.
    
    Features:
    - All-pairs shortest path
    - Negative cycle detection
    - Path reconstruction
    - Transitive closure
    - Connectivity analysis
    """
    
    def __init__(self, V: int):
        self.V = V
        self.INF = float('inf')
        self.graph = [[self.INF] * V for _ in range(V)]
        for i in range(V):
            self.graph[i][i] = 0
    
    def add_edge(self, u: int, v: int, weight: float):
        """Add directed edge u → v."""
        self.graph[u][v] = weight
    
    def run(self) -> FloydWarshallResult:
        """
        Run Floyd-Warshall algorithm.
        
        Returns comprehensive result with:
        - Distance matrix
        - Path reconstruction matrix
        - Negative cycle detection
        - Which pairs are affected by negative cycles
        """
        V = self.V
        INF = self.INF
        
        # Initialize matrices
        dist = [[self.graph[i][j] for j in range(V)] for i in range(V)]
        next_v = [[-1] * V for _ in range(V)]
        
        for i in range(V):
            for j in range(V):
                if dist[i][j] != INF and i != j:
                    next_v[i][j] = j
        
        # Main algorithm
        for k in range(V):
            for i in range(V):
                for j in range(V):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        if dist[i][k] + dist[k][j] < dist[i][j]:
                            dist[i][j] = dist[i][k] + dist[k][j]
                            next_v[i][j] = next_v[i][k]
        
        # Negative cycle detection
        has_negative_cycle = any(dist[i][i] < 0 for i in range(V))
        
        # Find which pairs are affected by negative cycles
        affected = [[False] * V for _ in range(V)]
        if has_negative_cycle:
            # If i → k → j and k is in negative cycle, then dist[i][j] = -inf
            for k in range(V):
                if dist[k][k] < 0:  # k is in negative cycle
                    for i in range(V):
                        for j in range(V):
                            if dist[i][k] != INF and dist[k][j] != INF:
                                affected[i][j] = True
        
        return FloydWarshallResult(
            dist=dist,
            next_vertex=next_v,
            has_negative_cycle=has_negative_cycle,
            affected_by_cycle=affected
        )
    
    def get_path(self, result: FloydWarshallResult, start: int, end: int) -> Optional[List[int]]:
        """Reconstruct shortest path."""
        if result.affected_by_cycle[start][end]:
            return None  # Path goes through negative cycle
        
        if result.next_vertex[start][end] == -1:
            return None
        
        path = [start]
        current = start
        visited = {start}
        
        while current != end:
            current = result.next_vertex[current][end]
            if current == -1 or current in visited:
                return None
            path.append(current)
            visited.add(current)
        
        return path
    
    def transitive_closure(self) -> List[List[bool]]:
        """
        Compute transitive closure (reachability matrix).
        reach[i][j] = True if there's a path from i to j.
        
        Uses Warshall's algorithm (simplified Floyd-Warshall).
        """
        V = self.V
        reach = [[False] * V for _ in range(V)]
        
        # Initialize
        for i in range(V):
            for j in range(V):
                reach[i][j] = (i == j) or (self.graph[i][j] != self.INF)
        
        # Warshall's algorithm
        for k in range(V):
            for i in range(V):
                for j in range(V):
                    reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
        
        return reach
    
    def find_diameter(self, result: FloydWarshallResult) -> Tuple[float, int, int]:
        """
        Find graph diameter (longest shortest path).
        
        Returns: (diameter, from_vertex, to_vertex)
        """
        V = self.V
        max_dist = -float('inf')
        from_v, to_v = -1, -1
        
        for i in range(V):
            for j in range(V):
                if (not result.affected_by_cycle[i][j] and 
                    result.dist[i][j] != float('inf') and
                    result.dist[i][j] > max_dist):
                    max_dist = result.dist[i][j]
                    from_v, to_v = i, j
        
        return (max_dist, from_v, to_v)
    
    def find_center(self, result: FloydWarshallResult) -> int:
        """
        Find graph center (vertex with minimum eccentricity).
        Eccentricity = max distance to any other vertex.
        """
        V = self.V
        min_eccentricity = float('inf')
        center = -1
        
        for i in range(V):
            eccentricity = 0
            valid = True
            
            for j in range(V):
                if result.affected_by_cycle[i][j]:
                    valid = False
                    break
                if result.dist[i][j] != float('inf'):
                    eccentricity = max(eccentricity, result.dist[i][j])
            
            if valid and eccentricity < min_eccentricity:
                min_eccentricity = eccentricity
                center = i
        
        return center


# ============================================
# REAL-WORLD: NETWORK CONNECTIVITY ANALYSIS
# ============================================

def analyze_network(
    nodes: List[str],
    connections: List[Tuple[str, str, float]]
) -> dict:
    """
    Analyze network connectivity.
    
    Args:
        nodes: ["router_a", "router_b", ...]
        connections: [("router_a", "router_b", latency_ms), ...]
    
    Returns:
        Network analysis report
    """
    node_to_idx = {name: i for i, name in enumerate(nodes)}
    V = len(nodes)
    
    fw = FloydWarshall(V)
    for src, dst, weight in connections:
        fw.add_edge(node_to_idx[src], node_to_idx[dst], weight)
    
    result = fw.run()
    reach = fw.transitive_closure()
    diameter_val, from_v, to_v = fw.find_diameter(result)
    center = fw.find_center(result)
    
    # Count unreachable pairs
    unreachable = sum(
        1 for i in range(V) for j in range(V) 
        if i != j and not reach[i][j]
    )
    
    return {
        "total_nodes": V,
        "diameter": diameter_val,
        "diameter_endpoints": (nodes[from_v], nodes[to_v]) if from_v >= 0 else None,
        "center_node": nodes[center] if center >= 0 else None,
        "unreachable_pairs": unreachable,
        "is_strongly_connected": unreachable == 0,
        "has_negative_cycle": result.has_negative_cycle
    }


# ============================================
# USAGE EXAMPLE
# ============================================

if __name__ == "__main__":
    # Example 1: Basic Floyd-Warshall
    print("=== Floyd-Warshall: Basic ===")
    fw = FloydWarshall(4)
    fw.add_edge(0, 1, 3)
    fw.add_edge(0, 3, 7)
    fw.add_edge(1, 0, 8)
    fw.add_edge(1, 2, 2)
    fw.add_edge(2, 0, 5)
    fw.add_edge(2, 3, 1)
    fw.add_edge(3, 0, 2)
    
    result = fw.run()
    
    print("Distance Matrix:")
    for i, row in enumerate(result.dist):
        print(f"  {i}: {[f'{d:.0f}' if d != float('inf') else '∞' for d in row]}")
    
    print(f"\nPath 1 → 3: {fw.get_path(result, 1, 3)}")
    
    # Example 2: Network Analysis
    print("\n=== Network Connectivity Analysis ===")
    nodes = ["HQ", "Branch_A", "Branch_B", "Cloud", "DR_Site"]
    connections = [
        ("HQ", "Branch_A", 10),
        ("HQ", "Branch_B", 15),
        ("HQ", "Cloud", 5),
        ("Branch_A", "HQ", 10),
        ("Branch_A", "Cloud", 8),
        ("Branch_B", "HQ", 15),
        ("Branch_B", "DR_Site", 20),
        ("Cloud", "HQ", 5),
        ("Cloud", "Branch_A", 8),
        ("Cloud", "DR_Site", 12),
        ("DR_Site", "Branch_B", 20),
        ("DR_Site", "Cloud", 12),
    ]
    
    report = analyze_network(nodes, connections)
    for key, value in report.items():
        print(f"  {key}: {value}")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280

Complexity Analysis

Aspect	Complexity	Notes
Time	$O (V^{3})$	Triple nested loop
Space	$O (V^{2})$	Distance matrix
Path reconstruction	$O (V)$	Follow next pointers

Floyd-Warshall vs Alternatives

Approach	Time	Best for
Dijkstra × V	$O (V^{2} \log V + V E)$	Sparse, non-negative
Bellman-Ford × V	$O (V^{2} E)$	Sparse, negative allowed
Floyd-Warshall	$O (V^{3})$	Dense, all-pairs needed
Johnson's	$O (V^{2} \log V + V E)$	Sparse, negative allowed

Key Takeaways

⚠️ Loop Order Matters!

python

# ✅ CORRECT: k is outermost
for k in range(V):
    for i in range(V):
        for j in range(V):
            ...

# ❌ WRONG: k inside
for i in range(V):
    for j in range(V):
        for k in range(V):
            ...  # Different algorithm!

💡 HPN's Rule

"Dense graph + all-pairs = Floyd-Warshall. Sparse graph = Dijkstra/Bellman-Ford × V."

Floyd-Warshall Algorithm - The All-Pairs Master ​

Problem Statement ​

When to Use ​

Real-World Applications ​

Core Concept: Dynamic Programming ​

2D Matrix Visualization ​

Implementation ​

Basic Floyd-Warshall ​

With Negative Cycle Detection ​

With Path Reconstruction ​

Production Code ​

Complexity Analysis ​

Floyd-Warshall vs Alternatives ​

Key Takeaways ​

Floyd-Warshall Algorithm - The All-Pairs Master

Problem Statement

When to Use

Real-World Applications

Core Concept: Dynamic Programming

2D Matrix Visualization

Implementation

Basic Floyd-Warshall

With Negative Cycle Detection

With Path Reconstruction

Production Code

Complexity Analysis

Floyd-Warshall vs Alternatives

Key Takeaways