Hướng dẫn giải của Đường đi ngắn nhất
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tìm đường đi ngắn nhất giữa hai đỉnh s và t trong đồ thị vô hướng có trọng số dương. Với n (≤ 2500) đỉnh và m (≤ 6200) cạnh, ta cần tìm tổng trọng số nhỏ nhất của đường đi từ s đến t. Đồ thị có thể có nhiều cạnh giữa hai đỉnh giống nhau, nhưng Dijkstra vẫn hoạt động chính xác. Dữ liệu đảm bảo luôn có đường đi.
Các cách tiếp cận
Cách Thuật toán Dijkstra
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, s, t;
cin >> n >> m >> s >> t;
vector<vector<pair<int, ll>>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
ll w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<ll> dist(n + 1, INF);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto &pr : adj[u]) {
int v = pr.first;
ll w = pr.second;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
cout << dist[t] << endl;
return 0;
}
- Time Complexity: O(m log n)
- Space Complexity: O(n + m)
Đây là thuật toán chuẩn để giải bài toán đường đi ngắn nhất có trọng số dương. Ta dùng priority queue (min-heap) để lấy ra đỉnh có khoảng cách ngắn nhất chưa xét. Với mỗi đỉnh, ta cập nhật khoảng cách cho các hàng xóm. Độ phức tạp là O(m log n) do mỗi cạnh được xử lý tối đa một lần trong khi mỗi lần push/pop heap tốn O(log n).
Cách Dijkstra với mảng thường (Fibonacci Heap)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, s, t;
cin >> n >> m >> s >> t;
vector<vector<pair<int, ll>>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
ll w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<ll> dist(n + 1, INF);
vector<bool> visited(n + 1, false);
dist[s] = 0;
for (int i = 0; i < n; i++) {
int u = -1;
ll minDist = INF;
for (int j = 1; j <= n; j++) {
if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
u = j;
}
}
if (u == -1) break;
visited[u] = true;
for (auto &pr : adj[u]) {
int v = pr.first;
ll w = pr.second;
if (!visited[v] && dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
}
}
}
cout << dist[t] << endl;
return 0;
}
- Time Complexity: O(n^2 + m)
- Space Complexity: O(n + m)
Thay vì dùng priority queue, ta dùng mảng để tìm đỉnh có khoảng cách nhỏ nhất chưa xét. Cách này đơn giản hơn về code nhưng chậm hơn với đồ thị thưa (dense). Tuy nhiên, với n=2500, độ phức tạp O(n^2) ~ 6.25 triệu thao tác vẫn có thể chấp nhận được. Ưu điểm là không cần cấu trúc dữ liệu phức tạp và thường nhanh hơn với đồ thị dày (dense graph).
Cách Độ phức tạp O(m log n) với vector pair
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 2505;
const ll INF = 1e18;
vector<pair<int, ll>> adj[MAXN];
ll dist[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, s, t;
cin >> n >> m >> s >> t;
for (int i = 0; i < m; i++) {
int u, v;
ll w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for (int i = 1; i <= n; i++) dist[i] = INF;
dist[s] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d != dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
cout << dist[t] << '\n';
return 0;
}
- Time Complexity: O(m log n)
- Space Complexity: O(n + m)
Phiên bản Dijkstra sử dụng vector全局 cho danh sách kề và mảng khoảng cách. Code ngắn gọn, dễ đọc. Với n=2500 và m=6200, thuật toán chạy rất nhanh. Cần chú ý dùng 'long long' cho trọng số (lên tới 10^9) và INF đủ lớn để không bị tràn số khi cộng.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(m log n) | O(n + m) | Thuật toán Dijkstra |
| 2 | O(n^2 + m) | O(n + m) | Dijkstra với mảng thường (Fibonacci Heap) |
| 3 | O(m log n) | O(n + m) | Độ phức tạp O(m log n) với vector pair |
Bài học kinh nghiệm
- Sử dụng priority queue (min-heap) là cách hiệu quả nhất cho đồ thị thưa (m << n^2)
- Luôn dùng 'long long' cho khoảng cách vì w ≤ 10^9 và có thể cộng nhiều cạnh
- Kiểm tra 'if (d > dist[u]) continue' để loại bỏ các bản ghi cũ trong heap
Lỗi thường gặp
- Quên dùng 'long long'導致 tràn số (overflow) khi cộng các trọng số lớn
- Không xử lý đúng đồ thị vô hướng - cần thêm cạnh cả hai chiều
- Dùng INF quá nhỏ (ví dụ 1e9) có thể không đủ khi tổng đường đi > 1e9
Bình luận