Giao diện
⚖️ Bellman-Ford — Handling Negative Weights
Bellman-Ford tìm đường đi ngắn nhất trong đồ thị có trọng số âm và phát hiện chu trình âm.
Khi nào cần Bellman-Ford?
┌─────────────────────────────────────────────────────────────────┐
│ NEGATIVE WEIGHTS IN REAL WORLD │
├─────────────────────────────────────────────────────────────────┤
│ │
│ 🎫 CURRENCY ARBITRAGE │
│ ───────────────────── │
│ USD → EUR → JPY → USD có thể tạo lợi nhuận (negative cost) │
│ │
│ 💰 FINANCIAL NETWORKS │
│ ───────────────────── │
│ Transactions có thể có rebates (hoàn tiền) │
│ │
│ 🔋 ENERGY NETWORKS │
│ ─────────────────── │
│ Một số đường dây có thể SINH điện (negative cost) │
│ │
│ 🌐 NETWORK ROUTING │
│ ───────────────── │
│ Một số paths có thể có bonuses/discounts │
│ │
└─────────────────────────────────────────────────────────────────┘Tại sao Dijkstra thất bại?
DIJKSTRA FAILS WITH NEGATIVE EDGES
───────────────────────────────────
2
A ─────────► B
\ │
5 \ │ -4 ← NEGATIVE!
\ ▼
──────► C
Dijkstra's approach:
1. Start at A (dist[A]=0)
2. Process B: dist[B] = 2 ← LOCKED!
3. Process C: dist[C] = 5
But via C→B: dist[B] should be 5 + (-4) = 1 < 2
Dijkstra đã "khóa" B trước khi tìm đường tốt hơnBellman-Ford Concept
Edge Relaxation
Relaxation: Nếu đi qua edge giảm được distance → cập nhật.
cpp
// Relax edge (u, v) with weight w
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}Algorithm
- Khởi tạo:
dist[source] = 0,dist[others] = ∞ - Lặp V-1 lần: Relax tất cả edges
- Lần thứ V: Nếu còn có thể relax → có chu trình âm!
Step-by-step Visualization
┌─────────────────────────────────────────────────────────────────┐
│ BELLMAN-FORD STEP-BY-STEP │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Graph (4 vertices, 5 edges): │
│ Edges: (0,1,4), (0,2,5), (1,2,-3), (2,3,4), (1,3,2) │
│ │
│ 4 │
│ 0 ─────────► 1 │
│ │ │ \ │
│ 5 │ -3 │ \ 2 │
│ ▼ ▼ ▼ │
│ 2 ─────────► 3 │
│ 4 │
│ │
│ Initial: dist = [0, ∞, ∞, ∞] │
│ │
│ Iteration 1: Relax all edges │
│ - (0,1,4): dist[1] = 0+4 = 4 │
│ - (0,2,5): dist[2] = 0+5 = 5 │
│ - (1,2,-3): dist[2] = min(5, 4-3) = 1 ← Updated! │
│ - (2,3,4): dist[3] = 1+4 = 5 │
│ - (1,3,2): dist[3] = min(5, 4+2) = 5 │
│ dist = [0, 4, 1, 5] │
│ │
│ Iteration 2: Relax all edges │
│ - No changes (already optimal) │
│ dist = [0, 4, 1, 5] │
│ │
│ Iteration 3 (V-1=3): No changes → Done! │
│ │
│ Check for negative cycle: No more relaxation → No cycle │
│ │
└─────────────────────────────────────────────────────────────────┘Implementation
cpp
#include <iostream>
#include <vector>
#include <limits>
struct Edge {
int from, to, weight;
};
class Graph {
int V;
std::vector<Edge> edges;
public:
explicit Graph(int vertices) : V(vertices) {}
void addEdge(int u, int v, int w) {
edges.push_back({u, v, w});
}
// Returns {distances, hasNegativeCycle}
std::pair<std::vector<int>, bool> bellmanFord(int source) {
const int INF = std::numeric_limits<int>::max();
std::vector<int> dist(V, INF);
dist[source] = 0;
// Relax all edges V-1 times
for (int i = 0; i < V - 1; ++i) {
bool updated = false;
for (const auto& e : edges) {
if (dist[e.from] != INF &&
dist[e.from] + e.weight < dist[e.to]) {
dist[e.to] = dist[e.from] + e.weight;
updated = true;
}
}
// Early termination if no updates
if (!updated) break;
}
// Check for negative cycle (V-th iteration)
for (const auto& e : edges) {
if (dist[e.from] != INF &&
dist[e.from] + e.weight < dist[e.to]) {
// Still can relax → negative cycle exists!
return {dist, true};
}
}
return {dist, false};
}
};
int main() {
Graph g(4);
g.addEdge(0, 1, 4);
g.addEdge(0, 2, 5);
g.addEdge(1, 2, -3); // Negative weight!
g.addEdge(2, 3, 4);
g.addEdge(1, 3, 2);
auto [dist, hasNegCycle] = g.bellmanFord(0);
if (hasNegCycle) {
std::cout << "Graph contains negative cycle!\n";
} else {
std::cout << "Shortest distances from node 0:\n";
for (int i = 0; i < 4; ++i) {
std::cout << "To " << i << ": " << dist[i] << "\n";
}
}
return 0;
}Output:
Shortest distances from node 0:
To 0: 0
To 1: 4
To 2: 1
To 3: 5Negative Cycle Detection
┌─────────────────────────────────────────────────────────────────┐
│ NEGATIVE CYCLE │
├─────────────────────────────────────────────────────────────────┤
│ │
│ A negative cycle: Tổng trọng số < 0 │
│ │
│ 2 │
│ A ─────────► B │
│ ▲ │ │
│ -4│ │ 1 │
│ │ ▼ │
│ D ◄───────── C │
│ -2 │
│ │
│ Cycle: B → C → D → A → B │
│ Total: 1 + (-2) + (-4) + 2 = -3 < 0 │
│ │
│ ⚠️ Shortest path = -∞ (đi vòng mãi để giảm distance) │
│ │
└─────────────────────────────────────────────────────────────────┘cpp
// Test negative cycle detection
Graph g(4);
g.addEdge(0, 1, 2);
g.addEdge(1, 2, 1);
g.addEdge(2, 3, -2);
g.addEdge(3, 0, -4); // Creates negative cycle!
auto [dist, hasNegCycle] = g.bellmanFord(0);
if (hasNegCycle) {
std::cout << "⚠️ Negative cycle detected!\n";
// No valid shortest path exists
}Complete Example với Path
cpp
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
struct Edge {
int from, to, weight;
};
class Graph {
int V;
std::vector<Edge> edges;
public:
explicit Graph(int v) : V(v) {}
void addEdge(int u, int v, int w) {
edges.push_back({u, v, w});
}
void bellmanFord(int src, int dest) {
const int INF = std::numeric_limits<int>::max();
std::vector<int> dist(V, INF), parent(V, -1);
dist[src] = 0;
// V-1 iterations
for (int i = 0; i < V - 1; ++i) {
for (const auto& e : edges) {
if (dist[e.from] != INF &&
dist[e.from] + e.weight < dist[e.to]) {
dist[e.to] = dist[e.from] + e.weight;
parent[e.to] = e.from;
}
}
}
// Check negative cycle
for (const auto& e : edges) {
if (dist[e.from] != INF &&
dist[e.from] + e.weight < dist[e.to]) {
std::cout << "⚠️ Negative cycle exists!\n";
return;
}
}
// Print result
if (dist[dest] == INF) {
std::cout << "No path from " << src << " to " << dest << "\n";
} else {
std::cout << "Shortest distance: " << dist[dest] << "\n";
std::vector<int> path;
for (int v = dest; v != -1; v = parent[v]) {
path.push_back(v);
}
std::reverse(path.begin(), path.end());
std::cout << "Path: ";
for (size_t i = 0; i < path.size(); ++i) {
std::cout << path[i];
if (i < path.size() - 1) std::cout << " → ";
}
std::cout << "\n";
}
}
};
int main() {
Graph g(5);
// Currency exchange rates (log-transformed to costs)
// Negative weight = profitable exchange
g.addEdge(0, 1, 4); // USD → EUR
g.addEdge(0, 2, 2); // USD → GBP
g.addEdge(1, 2, -1); // EUR → GBP (profit!)
g.addEdge(2, 3, 3); // GBP → JPY
g.addEdge(1, 3, 5); // EUR → JPY
g.addEdge(3, 4, 1); // JPY → CHF
std::cout << "💱 Currency Exchange Optimization:\n\n";
g.bellmanFord(0, 4); // USD → CHF
return 0;
}Output:
💱 Currency Exchange Optimization:
Shortest distance: 6
Path: 0 → 2 → 3 → 4Dijkstra vs Bellman-Ford
┌─────────────────────────────────────────────────────────────────┐
│ COMPARISON │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Aspect Dijkstra Bellman-Ford │
│ ────── ──────── ──────────── │
│ Time O((V+E)logV) O(V×E) │
│ Negative weights ❌ No ✅ Yes │
│ Negative cycles ❌ Fails ✅ Detects │
│ Data structure Priority Queue Simple array │
│ Best for Sparse, +weights Neg weights, cycles │
│ │
│ Rule of thumb: │
│ - Use Dijkstra if all weights ≥ 0 │
│ - Use Bellman-Ford if negative weights exist │
│ │
└─────────────────────────────────────────────────────────────────┘Complexity Analysis
| Aspect | Complexity |
|---|---|
| Time | O(V × E) |
| Space | O(V) |
| Why V-1 iterations? | Shortest path has at most V-1 edges |
📚 Tổng kết
| Aspect | Bellman-Ford |
|---|---|
| Type | Dynamic Programming |
| Data Structure | Edge list |
| Time | O(V × E) |
| Negative Weights | ✅ Yes |
| Negative Cycle | ✅ Can detect |
🎯 Graph Algorithms Complete!
Bạn đã hoàn thành Module 6: Graph Algorithms:
Part 1: Representation & Traversal
- Graph Representation (Matrix vs List)
- BFS (Breadth-First Search)
- DFS (Depth-First Search)
Part 2: Shortest Paths
- Dijkstra (priority_queue)
- Bellman-Ford (negative weights)