Tìm đường đi ngắn nhất

đã đăng vào 1 tháng 4 năm 2025, 12:07 a.m.

🛣️ Cheatsheet Các Thuật Toán Tìm Đường Đi Ngắn Nhất

📘 Giới thiệu

Ba thuật toán tìm đường đi ngắn nhất phổ biến nhất trong đồ thị là:

  • Dijkstra: Tìm đường đi ngắn nhất từ 1 đỉnh đến các đỉnh còn lại, không có cạnh âm.
  • Bellman-Ford: Xử lý được cạnh âm, phát hiện chu trình âm.
  • Floyd-Warshall: Tìm đường đi ngắn nhất giữa mọi cặp đỉnh.

📌 So sánh nhanh

Thuật toán Cạnh âm Chu trình âm Đồ thị dày Đồ thị thưa Độ phức tạp
Dijkstra ❌ ❌ ❌ ✅ O((V + E) log V)
Bellman-Ford ✅ ✅ ✅ ✅ O(V * E)
Floyd-Warshall ✅ ✅ ✅ ❌ O(V³)

1. 🚀 Dijkstra (với hàng đợi ưu tiên)

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
const int INF = 1e9;

vector<int> dijkstra(int start, int n, vector<vector<pii>>& adj) {
    vector<int> dist(n + 1, INF);
    priority_queue<pii, vector<pii>, greater<>> pq;
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (du > 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});
            }
        }
    }
    return dist;
}
✅ Ưu điểm:
  • Rất nhanh với đồ thị không có cạnh âm.
  • Có thể dùng set, priority_queue hoặc pairing_heap.
❌ Nhược điểm:
  • Không hoạt động đúng với cạnh âm.

2. 🐌 Bellman-Ford

vector<int> bellman_ford(int start, int n, vector<tuple<int, int, int>>& edges) {
    const int INF = 1e9;
    vector<int> dist(n + 1, INF);
    dist[start] = 0;

    for (int i = 1; i < n; ++i) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // Kiểm tra chu trình âm
    for (auto [u, v, w] : edges) {
        if (dist[u] != INF && dist[v] > dist[u] + w)
            throw runtime_error("Negative cycle detected");
    }

    return dist;
}
✅ Ưu điểm:
  • Hoạt động với cạnh âm.
  • Phát hiện chu trình âm.
❌ Nhược điểm:
  • Chậm với đồ thị lớn.

3. 🧠 Floyd-Warshall

void floyd_warshall(int n, vector<vector<int>>& dist) {
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (dist[i][k] < 1e9 && dist[k][j] < 1e9)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
✅ Ưu điểm:
  • Tìm đường đi ngắn nhất giữa mọi cặp đỉnh.
  • Dễ cài đặt.
❌ Nhược điểm:
  • Độ phức tạp O(V³) → chậm với đồ thị lớn.

🧪 Khi nào dùng thuật toán nào?

Tình huống Thuật toán gợi ý
Đường đi ngắn nhất từ 1 đỉnh, không cạnh âm Dijkstra
Đường đi ngắn nhất từ 1 đỉnh, có cạnh âm Bellman-Ford
Tìm đường ngắn nhất giữa mọi cặp đỉnh Floyd-Warshall
Cần phát hiện chu trình âm Bellman-Ford / FW

🔧 Tối ưu khi dùng

  • Với Dijkstra:

    • Sử dụng priority_queue hoặc set để tăng tốc độ.
    • Khi dùng cho lưới (grid), có thể thay bằng BFS nếu trọng số = 1.

  • Với Bellman-Ford:

    • Dừng sớm nếu không có cập nhật sau 1 lượt lặp.
    • Dùng để detect chu trình âm trong Competitive Programming.

  • Với Floyd-Warshall:

    • Dùng ma trận dist[i][j] và next[i][j] để reconstruct đường đi.
    • Có thể dùng với đồ thị nhỏ (V ≤ 500).

📚 Tài liệu tham khảo

Nhận xét

Không có ý kiến tại thời điểm này.