Giao diện
🗺️ Dijkstra — Shortest Path Algorithm
Dijkstra là thuật toán tiêu chuẩn vàng để tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh khác trong đồ thị có trọng số không âm.
Analogy: Google Maps
┌─────────────────────────────────────────────────────────────────┐
│ GOOGLE MAPS ANALOGY │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Bạn muốn đi từ NHÀ đến CÔNG TY: │
│ │
│ 5km │
│ NHÀ ─────────── Quận 1 │
│ │ │ │
│ 3km│ │2km │
│ │ │ │
│ Quận 3 ──────── Quận 7 ──────── CÔNG TY │
│ 4km 3km │
│ │
│ Google Maps tìm đường ngắn nhất: │
│ NHÀ → Quận 3 → Quận 7 → CÔNG TY = 3 + 4 + 3 = 10km │
│ │
│ Dijkstra làm việc tương tự: │
│ - Bắt đầu từ nguồn (NHÀ) │
│ - Mở rộng sang đỉnh GẦN NHẤT chưa xét │
│ - Cập nhật khoảng cách đến các đỉnh kề │
│ - Lặp lại cho đến khi đến đích │
│ │
└─────────────────────────────────────────────────────────────────┘Weighted Graph mẫu
SAMPLE WEIGHTED GRAPH
─────────────────────
10
0 ─────────► 1
│ │
5 │ │ 1
▼ 3 ▼
2 ─────────► 3
│ │
2 │ │ 4
▼ 9 ▼
4 ─────────► 5
Find shortest path from 0 to all verticesDijkstra's Algorithm
Concept: Greedy Approach
Dijkstra chọn đỉnh gần nhất chưa xét và cập nhật khoảng cách đến các đỉnh kề.
Algorithm Steps
- Khởi tạo:
dist[source] = 0,dist[others] = ∞ - Đưa source vào priority queue (min-heap)
- Lấy đỉnh có distance nhỏ nhất từ queue
- Với mỗi đỉnh kề, nếu đường qua đỉnh hiện tại ngắn hơn → cập nhật
- Lặp lại bước 3-4 cho đến khi queue rỗng
Step-by-step Visualization
┌─────────────────────────────────────────────────────────────────┐
│ DIJKSTRA STEP-BY-STEP │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Graph: 0 ──(10)──► 1 │
│ │ │ │
│ (5)│ │(1) │
│ ▼ (3) ▼ │
│ 2 ─────────► 3 │
│ │
│ Initial: dist = [0, ∞, ∞, ∞] │
│ │
│ Step 1: Process node 0 (dist=0) │
│ Update: dist[1] = 0+10 = 10 │
│ Update: dist[2] = 0+5 = 5 │
│ dist = [0, 10, 5, ∞] │
│ │
│ Step 2: Process node 2 (dist=5) ← smallest unvisited │
│ Update: dist[3] = 5+3 = 8 │
│ dist = [0, 10, 5, 8] │
│ │
│ Step 3: Process node 3 (dist=8) │
│ No updates needed │
│ │
│ Step 4: Process node 1 (dist=10) │
│ dist[3] via 1 = 10+1 = 11 > 8 → No update │
│ │
│ Final: dist = [0, 10, 5, 8] │
│ Shortest path from 0: │
│ - To 1: 10 (0→1) │
│ - To 2: 5 (0→2) │
│ - To 3: 8 (0→2→3) │
│ │
└─────────────────────────────────────────────────────────────────┘Implementation với priority_queue
cpp
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
class Graph {
int V;
// adjacency list: {neighbor, weight}
std::vector<std::vector<std::pair<int, int>>> adj;
public:
explicit Graph(int vertices) : V(vertices), adj(vertices) {}
void addEdge(int u, int v, int weight) {
adj[u].push_back({v, weight});
// adj[v].push_back({u, weight}); // Uncomment for undirected
}
std::vector<int> dijkstra(int source) {
const int INF = std::numeric_limits<int>::max();
std::vector<int> dist(V, INF);
// Min-heap: {distance, vertex}
// std::greater makes it a min-heap
std::priority_queue<
std::pair<int, int>,
std::vector<std::pair<int, int>>,
std::greater<std::pair<int, int>>
> pq;
dist[source] = 0;
pq.push({0, source});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
// Skip if we've found a better path already
if (d > dist[u]) continue;
// Relax edges
for (auto [v, weight] : adj[u]) {
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
return dist;
}
};
int main() {
Graph g(4);
g.addEdge(0, 1, 10);
g.addEdge(0, 2, 5);
g.addEdge(2, 3, 3);
g.addEdge(1, 3, 1);
auto dist = g.dijkstra(0);
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: 10
To 2: 5
To 3: 8Path Reconstruction
Để khôi phục đường đi, lưu thêm mảng parent:
cpp
struct DijkstraResult {
std::vector<int> dist;
std::vector<int> parent;
};
DijkstraResult dijkstraWithPath(int source) {
const int INF = std::numeric_limits<int>::max();
std::vector<int> dist(V, INF);
std::vector<int> parent(V, -1);
std::priority_queue<
std::pair<int, int>,
std::vector<std::pair<int, int>>,
std::greater<>
> pq;
dist[source] = 0;
pq.push({0, source});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto [v, weight] : adj[u]) {
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
parent[v] = u; // Track parent
pq.push({dist[v], v});
}
}
}
return {dist, parent};
}
std::vector<int> getPath(int dest, const std::vector<int>& parent) {
std::vector<int> path;
for (int v = dest; v != -1; v = parent[v]) {
path.push_back(v);
}
std::reverse(path.begin(), path.end());
return path;
}Usage:
cpp
auto [dist, parent] = g.dijkstraWithPath(0);
auto path = getPath(3, parent);
std::cout << "Path to 3: ";
for (int v : path) {
std::cout << v << " ";
}
// Output: Path to 3: 0 2 3Complete Example với Path
cpp
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
class Graph {
int V;
std::vector<std::vector<std::pair<int, int>>> adj;
public:
explicit Graph(int v) : V(v), adj(v) {}
void addEdge(int u, int v, int w) {
adj[u].push_back({v, w});
adj[v].push_back({u, w}); // Undirected
}
void dijkstra(int src, int dest) {
const int INF = std::numeric_limits<int>::max();
std::vector<int> dist(V, INF), parent(V, -1);
std::priority_queue<
std::pair<int, int>,
std::vector<std::pair<int, int>>,
std::greater<>
> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
parent[v] = u;
pq.push({dist[v], v});
}
}
}
// Print result
if (dist[dest] == INF) {
std::cout << "No path from " << src << " to " << dest << "\n";
} else {
std::cout << "Shortest distance: " << dist[dest] << "\n";
// Reconstruct path
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 (int i = 0; i < path.size(); ++i) {
std::cout << path[i];
if (i < path.size() - 1) std::cout << " → ";
}
std::cout << "\n";
}
}
};
int main() {
Graph g(6);
// Build a city map
g.addEdge(0, 1, 5); // Nhà → Quận 1
g.addEdge(0, 2, 3); // Nhà → Quận 3
g.addEdge(1, 3, 2); // Quận 1 → Quận 7
g.addEdge(2, 3, 4); // Quận 3 → Quận 7
g.addEdge(3, 4, 3); // Quận 7 → Công ty
g.addEdge(1, 4, 6); // Quận 1 → Công ty (alternative)
std::cout << "🗺️ Google Maps Simulation:\n\n";
g.dijkstra(0, 4); // Nhà → Công ty
return 0;
}Output:
🗺️ Google Maps Simulation:
Shortest distance: 10
Path: 0 → 1 → 3 → 4Complexity Analysis
┌─────────────────────────────────────────────────────────────────┐
│ DIJKSTRA COMPLEXITY │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Implementation Time Space │
│ ────────────── ──── ───── │
│ Array (naive) O(V²) O(V) │
│ Binary Heap (priority_queue) O((V+E)logV) O(V) │
│ Fibonacci Heap O(VlogV + E) O(V) │
│ │
│ priority_queue là lựa chọn tốt nhất trong thực tế │
│ │
└─────────────────────────────────────────────────────────────────┘Limitation: No Negative Weights!
⚠️ CRITICAL
Dijkstra KHÔNG hoạt động với cạnh có trọng số âm!
WHY DIJKSTRA FAILS
──────────────────
1
0 ─────────► 1
│ │
4 │ │ -3 ← NEGATIVE!
▼ ▼
2 ◄───────── 3
2
Dijkstra finds: 0→1 = 1
But actual shortest: 0→2→3→1 = 4+2+(-3) = 3
Dijkstra đã "khóa" node 1 với dist=1
trước khi tìm ra đường ngắn hơn qua 2→3Với negative weights, dùng Bellman-Ford.
Real-world Applications
| Application | Description |
|---|---|
| Google Maps | Tìm đường ngắn nhất giữa 2 địa điểm |
| Network Routing | OSPF protocol trong routers |
| Games | Pathfinding cho AI characters |
| Flight Planning | Tìm route bay tối ưu |
📚 Tổng kết
| Aspect | Dijkstra |
|---|---|
| Type | Greedy |
| Data Structure | Priority Queue (min-heap) |
| Time | O((V+E) log V) |
| Negative Weights | ❌ Không hỗ trợ |
| Best for | Sparse graphs, non-negative weights |
➡️ Tiếp theo
Khi đồ thị có cạnh âm, chúng ta cần thuật toán khác...
Bellman-Ford → — Xử lý trọng số âm.