Giao diện
Floyd-Warshall Algorithm Advanced
Floyd-Warshall tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong O(V³).
Tại sao Floyd-Warshall?
┌─────────────────────────────────────────────────────────────────┐
│ FLOYD-WARSHALL USE CASES │
├─────────────────────────────────────────────────────────────────┤
│ │
│ 🗺️ DISTANCE MATRICES 🌐 NETWORK ANALYSIS │
│ ────────────────── ──────────────── │
│ All cities distances Connectivity metrics │
│ Precompute for queries Transitive closure │
│ │
│ 🔍 DETECT NEGATIVE CYCLES 🎮 GAME AI │
│ ──────────────────────── ────── │
│ Currency arbitrage All-pairs pathfinding │
│ Negative weight handling Cached distances │
│ │
└─────────────────────────────────────────────────────────────────┘Khi nào dùng Floyd-Warshall?
| Bài toán | Algorithm | Complexity |
|---|---|---|
| Single-source, positive weights | Dijkstra | O(E log V) |
| Single-source, negative weights | Bellman-Ford | O(VE) |
| All-pairs, any weights | Floyd-Warshall | O(V³) |
| All-pairs, positive weights | V × Dijkstra | O(VE log V) |
💡 RULE OF THUMB
Dùng Floyd-Warshall khi:
- Cần shortest path giữa mọi cặp đỉnh
- Graph dense (E ≈ V²)
- Có negative weights (không negative cycle)
- Cần detect negative cycle
Thuật toán
Dynamic Programming Recurrence
Định nghĩa dist[k][i][j] = shortest path từ i đến j, chỉ đi qua đỉnh {0, 1, ..., k-1} làm intermediate.
dist[k][i][j] = min(
dist[k-1][i][j], // Không đi qua k
dist[k-1][i][k] + dist[k-1][k][j] // Đi qua k
)┌─────────────────────────────────────────────────────────────────┐
│ FLOYD-WARSHALL IDEA │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Với mỗi intermediate vertex k: │
│ │
│ i ──────────────────────► j (không qua k) │
│ dist[i][j] │
│ │
│ i ─────► k ─────► j (qua k) │
│ dist[i][k] dist[k][j] │
│ │
│ Chọn đường ngắn hơn! │
│ │
└─────────────────────────────────────────────────────────────────┘Tối ưu Space: O(V²)
Vì chỉ cần dist[k-1] để tính dist[k], có thể reuse matrix:
cpp
for k from 0 to V-1:
for i from 0 to V-1:
for j from 0 to V-1:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])Implementation
cpp
#include <iostream>
#include <vector>
#include <climits>
#include <iomanip>
using namespace std;
const int INF = 1e9; // Use large value, not INT_MAX (avoid overflow)
class FloydWarshall {
private:
int V;
vector<vector<int>> dist;
vector<vector<int>> next_; // For path reconstruction
public:
FloydWarshall(int vertices) : V(vertices),
dist(V, vector<int>(V, INF)),
next_(V, vector<int>(V, -1)) {
// Distance to self = 0
for (int i = 0; i < V; ++i) {
dist[i][i] = 0;
}
}
void addEdge(int u, int v, int weight) {
dist[u][v] = weight;
next_[u][v] = v; // From u, go to v directly
}
// Main algorithm
bool compute() {
// Floyd-Warshall: O(V³)
for (int k = 0; k < V; ++k) {
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
// Avoid overflow: check if path exists
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];
next_[i][j] = next_[i][k]; // Update path
}
}
}
}
}
// Check for negative cycle: dist[i][i] < 0
for (int i = 0; i < V; ++i) {
if (dist[i][i] < 0) {
cout << "⚠️ Negative cycle detected!" << endl;
return false;
}
}
return true;
}
// Get shortest distance
int getDistance(int u, int v) const {
return dist[u][v];
}
// Reconstruct path
vector<int> getPath(int u, int v) const {
if (next_[u][v] == -1) return {}; // No path
vector<int> path;
int current = u;
while (current != v) {
path.push_back(current);
current = next_[current][v];
}
path.push_back(v);
return path;
}
// Print distance matrix
void printMatrix() const {
cout << "\nDistance Matrix:" << endl;
cout << " ";
for (int j = 0; j < V; ++j) {
cout << setw(5) << j;
}
cout << endl;
for (int i = 0; i < V; ++i) {
cout << setw(3) << i << ":";
for (int j = 0; j < V; ++j) {
if (dist[i][j] >= INF) {
cout << setw(5) << "INF";
} else {
cout << setw(5) << dist[i][j];
}
}
cout << endl;
}
}
};
int main() {
/*
Graph:
1
0 ──────► 1
│ │
5 │ │ 2
▼ ▼
2 ◄────── 3
1
And: 2 → 1 (weight 3)
*/
FloydWarshall fw(4);
fw.addEdge(0, 1, 1);
fw.addEdge(0, 2, 5);
fw.addEdge(1, 3, 2);
fw.addEdge(3, 2, 1);
fw.addEdge(2, 1, 3);
if (fw.compute()) {
fw.printMatrix();
cout << "\n--- Sample Queries ---" << endl;
// Query 1: 0 to 2
cout << "Distance 0 → 2: " << fw.getDistance(0, 2) << endl;
cout << "Path: ";
for (int v : fw.getPath(0, 2)) {
cout << v << " ";
}
cout << endl;
// Query 2: 0 to 3
cout << "\nDistance 0 → 3: " << fw.getDistance(0, 3) << endl;
cout << "Path: ";
for (int v : fw.getPath(0, 3)) {
cout << v << " ";
}
cout << endl;
}
return 0;
}Output:
Distance Matrix:
0 1 2 3
0: 0 1 4 3
1: INF 0 3 2
2: INF 3 0 5
3: INF 4 1 0
--- Sample Queries ---
Distance 0 → 2: 4
Path: 0 1 3 2
Distance 0 → 3: 3
Path: 0 1 3Negative Cycle Detection
cpp
// After running Floyd-Warshall
for (int i = 0; i < V; ++i) {
if (dist[i][i] < 0) {
// 🚨 Negative cycle exists!
// Vertex i is part of (or reachable from) a negative cycle
}
}Example: Currency Arbitrage
USD ──0.9──► EUR
▲ │
│ │
1.2 1.4
│ │
└── GBP ◄──┘
Cycle: USD → EUR → GBP → USD
0.9 × 1.4 × 1.2 = 1.512 > 1 → Arbitrage opportunity!
To detect: Use log(rate) → sum < 0 means product > 1
Or use -log(rate) → negative cycle = arbitrageTransitive Closure
Nếu chỉ cần biết "có đường đi hay không" (không cần khoảng cách):
cpp
// Warshall's algorithm (simpler variant)
vector<vector<bool>> reachable(V, vector<bool>(V, false));
// Initialize: direct edges
for each edge (u, v):
reachable[u][v] = true;
for each vertex i:
reachable[i][i] = true;
// Transitive closure
for (int k = 0; k < V; ++k) {
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
reachable[i][j] = reachable[i][j] ||
(reachable[i][k] && reachable[k][j]);
}
}
}Complexity Analysis
| Aspect | Complexity |
|---|---|
| Time | O(V³) — 3 nested loops |
| Space | O(V²) — Distance + Next matrices |
| Path Reconstruction | O(V) per query |
So sánh với V × Dijkstra/Bellman-Ford
| Approach | Time | Better when |
|---|---|---|
| Floyd-Warshall | O(V³) | Dense graph, E ≈ V² |
| V × Dijkstra | O(VE log V) | Sparse graph, positive weights |
| V × Bellman-Ford | O(V²E) | Sparse, negative weights |
💡 DECISION
- Dense graph (E ≈ V²): Floyd-Warshall wins
- Sparse graph (E ≈ V): V × Dijkstra wins (if no negative weights)
⚠️ Common Pitfalls
CẢNH BÁO
1. Integer overflow với INT_MAX:
cpp
// ❌ SAI: INT_MAX + weight = negative (overflow!)
if (dist[i][k] + dist[k][j] < dist[i][j]) { ... }
// ✅ ĐÚNG: Check trước khi cộng
const int INF = 1e9; // Không dùng INT_MAX
if (dist[i][k] < INF && dist[k][j] < INF) {
if (dist[i][k] + dist[k][j] < dist[i][j]) { ... }
}2. Thứ tự vòng lặp k-i-j:
cpp
// ❌ SAI: k phải là outermost loop!
for (int i = 0; i < V; ++i)
for (int j = 0; j < V; ++j)
for (int k = 0; k < V; ++k) // SAI!
// ✅ ĐÚNG: k phải ở ngoài cùng
for (int k = 0; k < V; ++k)
for (int i = 0; i < V; ++i)
for (int j = 0; j < V; ++j)3. Quên đường đi đến chính nó:
cpp
// ✅ Initialize dist[i][i] = 0
for (int i = 0; i < V; ++i) {
dist[i][i] = 0;
}🌐 Real-World Application: Network Latency
cpp
// Given: Latency between directly connected servers
// Find: Minimum latency between any two servers
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
int main() {
vector<string> servers = {
"US-East", "US-West", "EU-Central", "Asia-Tokyo"
};
int n = servers.size();
// Latency matrix (ms)
vector<vector<int>> latency = {
{0, 70, 100, 150}, // US-East
{70, 0, 130, 80}, // US-West
{100, 130, 0, 200}, // EU-Central
{150, 80, 200, 0} // Asia-Tokyo
};
// Floyd-Warshall
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
latency[i][j] = min(latency[i][j],
latency[i][k] + latency[k][j]);
}
}
}
// Print results
cout << "Optimal Latencies (ms):" << endl;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
cout << servers[i] << " ↔ " << servers[j]
<< ": " << latency[i][j] << "ms" << endl;
}
}
return 0;
}🎯 Practice Problems
| Problem | Difficulty | Focus |
|---|---|---|
| Find the City (LeetCode 1334) | Medium | Floyd-Warshall basic |
| Shortest Path Visiting All Nodes (LeetCode 847) | Hard | All-pairs + TSP |
| Floyd (CSES) | Medium | Template |
| Negative Cycle (CSES) | Medium | Cycle detection |