Bài 22.1: Thuật toán Floyd-Warshall tìm đường đi ngắn nhất

Chào mừng trở lại với series blog về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ lặn sâu vào một thuật toán cổ điển và mạnh mẽ giải quyết bài toán Tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong một đồ thị. Đó chính là Thuật toán Floyd-Warshall.

Trong các bài trước, chúng ta có thể đã gặp các thuật toán tìm đường đi ngắn nhất từ một đỉnh nguồn duy nhất như Dijkstra (cho trọng số không âm) hoặc Bellman-Ford (cho trọng số âm). Nhưng nếu mục tiêu của chúng ta là tìm khoảng cách ngắn nhất (và có thể là đường đi) giữa tất cả các cặp đỉnh trong đồ thị thì sao? Đây là lúc thuật toán Floyd-Warshall tỏa sáng!

Bài Toán: All-Pairs Shortest Path (APSP)

Bài toán All-Pairs Shortest Path (APSP) (Tìm đường đi ngắn nhất giữa mọi cặp đỉnh) được phát biểu như sau:

Cho một đồ thị có hướng và có trọng số $G = (V, E)$, với $V$ là tập hợp các đỉnh và $E$ là tập hợp các cạnh. Mỗi cạnh $(u, v) \in E$ có một trọng số $w(u, v)$. Chúng ta cần tìm độ dài (tổng trọng số) của đường đi ngắn nhất giữa mọi cặp đỉnh $(i, j)$ trong đồ thị.

Lưu ý: Trọng số cạnh có thể âm, nhưng đồ thị không được chứa chu trình âm (negative cycle) mà từ đó có thể đạt tới đích, nếu không thì đường đi ngắn nhất sẽ không xác định (có thể âm vô cùng).

Tại sao không chỉ chạy Dijkstra/Bellman-Ford nhiều lần?

Một cách tiếp cận trực quan là chạy thuật toán tìm đường đi ngắn nhất từ một đỉnh nguồn duy nhất cho mỗi đỉnh trong đồ thị.

Nếu tất cả trọng số đều không âm: Chúng ta có thể chạy thuật toán Dijkstra từ mỗi đỉnh $u \in V$. Nếu đồ thị được biểu diễn bằng danh sách kề và sử dụng min-priority queue, mỗi lần chạy Dijkstra mất $O(|E| \log |V|)$. Tổng cộng sẽ là $O(|V||E| \log |V|)$. Nếu dùng ma trận kề và priority queue dựa trên mảng, mỗi lần Dijkstra mất $O(|V|^2)$, tổng cộng $O(|V|^3)$.
Nếu có trọng số âm (nhưng không có chu trình âm): Chúng ta có thể chạy thuật toán Bellman-Ford từ mỗi đỉnh $u \in V$. Mỗi lần chạy Bellman-Ford mất $O(|V||E|)$. Tổng cộng sẽ là $O(|V|^2|E|)$.

Đối với đồ thị dày đặc (dense graph), nơi $|E|$ gần bằng $|V|^2$, chạy Dijkstra $|V|$ lần với biểu diễn ma trận kề sẽ có độ phức tạp $O(|V|^3)$, tương đương với Floyd-Warshall. Chạy Bellman-Ford $|V|$ lần cho đồ thị dày đặc sẽ là $O(|V|^4)$, kém hiệu quả hơn Floyd-Warshall.

Ngoài ra, Floyd-Warshall có vẻ ngoài đơn giản hơn khi triển khai (chỉ với 3 vòng lặp lồng nhau) so với việc quản lý priority queue hay kiểm tra $V-1$ lần trong Bellman-Ford khi chạy nó $|V|$ lần. Nó cũng xử lý trọng số âm một cách tự nhiên mà không cần các bước tiền xử lý phức tạp (như re-weighting trong Johnson's algorithm, một thuật toán APSP khác).

Ý Tưởng Cốt Lõi của Floyd-Warshall: Quy Hoạch Động

Floyd-Warshall là một ví dụ điển hình của quy hoạch động (dynamic programming). Ý tưởng chính dựa trên việc cải tiến dần dần các ước lượng về khoảng cách ngắn nhất bằng cách xem xét các đỉnh trung gian.

Thuật toán xây dựng một ma trận khoảng cách dist[i][j] biểu diễn độ dài đường đi ngắn nhất được biết tính đến thời điểm hiện tại từ đỉnh $i$ đến đỉnh $j$.

Trạng thái của quy hoạch động có thể được định nghĩa như sau: dist[k][i][j] là độ dài đường đi ngắn nhất từ đỉnh $i$ đến đỉnh $j$ chỉ sử dụng các đỉnh trong tập hợp {0, 1, ..., k-1} làm các đỉnh trung gian trên đường đi.

Mục tiêu cuối cùng của chúng ta là tìm dist[V][i][j] cho mọi cặp $(i, j)$, tức là đường đi ngắn nhất từ $i$ đến $j$ có thể đi qua bất kỳ đỉnh nào trong đồ thị {0, 1, ..., V-1} làm trung gian.

Để chuyển từ trạng thái dist[k-1][i][j] sang dist[k][i][j], chúng ta xét đỉnh $k-1$. Đường đi ngắn nhất từ $i$ đến $j$ chỉ sử dụng các đỉnh trong {0, ..., k-1} làm trung gian có thể là một trong hai loại:

Đường đi đó không sử dụng đỉnh $k-1$ làm đỉnh trung gian. Trong trường hợp này, đường đi ngắn nhất đó chỉ sử dụng các đỉnh trong {0, ..., k-2} làm trung gian. Độ dài của nó chính là dist[k-1][i][j].
Đường đi đó có sử dụng đỉnh $k-1$ làm đỉnh trung gian. Nếu vậy, đường đi ngắn nhất từ $i$ đến $j$ đi qua $k-1$ sẽ bao gồm đường đi ngắn nhất từ $i$ đến $k-1$ (chỉ sử dụng đỉnh trong {0, ..., k-2} làm trung gian) nối với đường đi ngắn nhất từ $k-1$ đến $j$ (cũng chỉ sử dụng đỉnh trong {0, ..., k-2} làm trung gian). Độ dài của đường đi này sẽ là dist[k-1][i][k-1] + dist[k-1][k-1][j].

Vậy, công thức truy hồi sẽ là: dist[k][i][j] = min( dist[k-1][i][j], dist[k-1][i][k-1] + dist[k-1][k-1][j] )

Với trạng thái ban đầu là dist[0][i][j] (đường đi ngắn nhất không sử dụng đỉnh trung gian nào), chính là trọng số của cạnh trực tiếp từ $i$ đến $j$ (hoặc 0 nếu $i=j$, hoặc vô cùng nếu không có cạnh trực tiếp).

Vì giá trị dist[k][i][j] chỉ phụ thuộc vào dist[k-1] và các chỉ số $i, j, k-1$, chúng ta có thể tối ưu không gian lưu trữ bằng cách chỉ sử dụng một ma trận 2D dist[V][V] và cập nhật nó tại chỗ. Vòng lặp ngoài cùng sẽ duyệt qua các đỉnh trung gian k (từ 0 đến V-1), sau đó là hai vòng lặp duyệt qua tất cả các cặp đỉnh nguồn i và đích j.

Công thức cập nhật tại chỗ sẽ là: dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] ) Điều này được thực hiện cho tất cả cặp $(i, j)$ sau khi đã cố định đỉnh trung gian $k$.

Thứ tự của các vòng lặp là cực kỳ quan trọng: Vòng lặp duyệt đỉnh trung gian k phải nằm ở ngoài cùng. Nếu vòng lặp k nằm bên trong, chúng ta có thể sử dụng một đường đi qua đỉnh k trước khi chúng ta đã tính toán được đường đi ngắn nhất tới k (hoặc từ k) chỉ sử dụng các đỉnh trung gian nhỏ hơn.

Các Bước Thuật Toán Floyd-Warshall

Khởi tạo ma trận khoảng cách:
- Tạo một ma trận dist[V][V] và khởi tạo nó.
- Đối với mọi cặp đỉnh $(i, j)$:
  - Nếu $i = j$, đặt `dist[i][j] = 0$.
  - Nếu có cạnh trực tiếp từ $i$ đến $j$ với trọng số $w(i, j)$, đặt `dist[i][j] = w(i, j)$.
  - Nếu không có cạnh trực tiếp từ $i$ đến $j$ và $i \neq j$, đặt dist[i][j] = INF (một giá trị vô cùng lớn biểu thị không có đường đi hoặc đường đi rất dài). Chú ý chọn INF đủ lớn để tránh tràn số khi cộng. INT_MAX / 2 hoặc một giá trị lớn hơn tổng trọng số tối đa có thể là an toàn.
Lặp qua các đỉnh trung gian:
- Duyệt qua tất cả các đỉnh k từ $0$ đến $V-1$ (đỉnh trung gian tiềm năng).
- Bên trong vòng lặp của k:
  - Duyệt qua tất cả các đỉnh nguồn i từ $0$ đến $V-1$.
  - Bên trong vòng lặp của i:
    - Duyệt qua tất cả các đỉnh đích j từ $0$ đến $V-1$.
    - Bên trong vòng lặp của j:
      - Kiểm tra xem đường đi từ $i$ đến $k$ và từ $k$ đến $j$ có tồn tại không (nghĩa là dist[i][k] và dist[k][j] không phải là INF).
      - Nếu có, so sánh khoảng cách hiện tại dist[i][j] với khoảng cách thông qua đỉnh trung gian k (dist[i][k] + dist[k][j]).
      - Cập nhật dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Cần cẩn thận tránh tràn số khi cộng hai giá trị INF hoặc INF với một số hữu hạn.
Kiểm tra chu trình âm (Tùy chọn nhưng quan trọng):
- Sau khi hoàn thành các bước trên, nếu dist[i][i] < 0 cho bất kỳ đỉnh i nào, điều đó có nghĩa là có một chu trình âm có thể đạt được từ đỉnh i (hoặc đạt tới đỉnh i). Trong trường hợp này, đường đi ngắn nhất liên quan đến các đỉnh trên chu trình âm đó là không xác định (có thể âm vô cùng).

Phân Tích Độ Phức Tạp

Thời gian: Ba vòng lặp lồng nhau, mỗi vòng lặp chạy $V$ lần. Do đó, độ phức tạp thời gian là O(V^3).
Không gian: Chúng ta sử dụng một ma trận 2D dist[V][V] để lưu trữ khoảng cách. Do đó, độ phức tạp không gian là O(V^2).

Triển Khai trong C++

Chúng ta sẽ xem xét một vài ví dụ triển khai trong C++:

Triển khai cơ bản để tính toán ma trận khoảng cách.
Triển khai có thêm khả năng truy vết đường đi.
Triển khai có kiểm tra chu trình âm.

Để biểu diễn vô cùng, chúng ta sẽ sử dụng một số nguyên lớn. Cần cẩn thận với việc cộng hai số lớn có thể gây tràn số. Một cách an toàn là sử dụng INT_MAX / 2 hoặc kiểm tra trước khi cộng.

Ví Dụ 1: Tính Toán Ma Trận Khoảng Cách Cơ Bản

#include <iostream>
#include <vector>
#include <algorithm>

const int INF = 1e9; // Biểu diễn vô cùng. Chọn giá trị đủ lớn nhưng nhỏ hơn INT_MAX/2 để tránh tràn số khi cộng.

void floydWarshall(std::vector<std::vector<int>>& graph) {
    int V = graph.size(); // Số lượng đỉnh
    std::vector<std::vector<int>> dist = graph; // Khởi tạo ma trận khoảng cách ban đầu từ ma trận kề

    // Bước 2: Lặp qua các đỉnh trung gian k
    for (int k = 0; k < V; ++k) {
        // Bước 2a: Lặp qua tất cả các đỉnh nguồn i
        for (int i = 0; i < V; ++i) {
            // Bước 2b: Lặp qua tất cả các đỉnh đích j
            for (int j = 0; j < V; ++j) {
                // Nếu đỉnh i hoặc đỉnh j không thể đạt được từ/đến đỉnh trung gian k
                // (dist[i][k] hoặc dist[k][j] là INF), thì không có đường đi qua k
                // hoặc đường đi đó không thể ngắn hơn đường đi hiện tại.
                // Cần kiểm tra để tránh tràn số khi cộng INF.
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    // Cập nhật khoảng cách nếu đường đi qua k ngắn hơn
                    dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // In ma trận khoảng cách cuối cùng
    std::cout << "Ma tran khoang cach ngan nhat giua moi cap dinh:\n";
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (dist[i][j] == INF) {
                std::cout << "INF ";
            } else {
                std::cout << dist[i][j] << "   ";
            }
        }
        std::cout << std::endl;
    }
}

int main() {
    // Ví dụ đồ thị 1 (không có trọng số âm)
    std::cout << "--- Do thi 1 (khong co trong so am) ---\n";
    std::vector<std::vector<int>> graph1 = {
        {0,   5,  INF, 10},
        {INF, 0,   3,  INF},
        {INF, INF, 0,   1},
        {INF, INF, INF, 0}
    }; // Kích thước V=4
    floydWarshall(graph1);
    std::cout << std::endl;

    // Ví dụ đồ thị 2 (có trọng số âm, không có chu trình âm)
    std::cout << "--- Do thi 2 (co trong so am, khong co chu trinh am) ---\n";
     std::vector<std::vector<int>> graph2 = {
        {0,   3,  8,   INF, -4},
        {INF, 0,  INF, 1,   7},
        {INF, 4,  0,   INF, INF},
        {2,   INF, -5,  0,   INF},
        {INF, INF, INF, 6,   0}
    }; // Kích thước V=5
    floydWarshall(graph2);

    return 0;
}

Giải thích Code Ví Dụ 1:

#include <iostream> và các thư viện: Bao gồm các thư viện cần thiết cho nhập xuất, vector và thuật toán (để sử dụng std::min).
const int INF = 1e9;: Định nghĩa một hằng số lớn để biểu diễn vô cùng. Chúng ta dùng 1e9 (1 tỷ) vì nó đủ lớn cho hầu hết các bài toán thực tế mà không gây tràn số khi cộng (ví dụ: 1 tỷ + 1 tỷ vẫn nhỏ hơn INT_MAX).
void floydWarshall(std::vector<std::vector<int>>& graph): Hàm chính triển khai thuật toán. Nó nhận vào ma trận kề của đồ thị.
std::vector<std::vector<int>> dist = graph;: Tạo một bản sao của ma trận kề. Ma trận dist này sẽ được cập nhật dần để chứa khoảng cách ngắn nhất. Ban đầu, dist[i][j] chứa trọng số cạnh trực tiếp từ $i$ đến $j$.
Ba vòng lặp lồng nhau: Đây là trái tim của thuật toán.
- Vòng ngoài cùng for (int k = 0; k < V; ++k): Duyệt qua các đỉnh k đóng vai trò là đỉnh trung gian.
- Hai vòng trong for (int i = 0; i < V; ++i) và for (int j = 0; j < V; ++j): Duyệt qua tất cả các cặp đỉnh nguồn i và đích j.
if (dist[i][k] != INF && dist[k][j] != INF): Kiểm tra xem có khả năng tồn tại đường đi từ $i$ đến $j$ đi qua đỉnh trung gian k hay không. Nếu một trong hai đoạn i -> k hoặc k -> j có khoảng cách là INF (vô cùng), nghĩa là không có đường đi, thì đường đi qua k không thể là đường đi hợp lệ (hoặc sẽ là vô cùng). Kiểm tra này cũng giúp tránh tràn số khi cộng INF với một số khác hoặc INF với INF.
dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);: Đây là bước cập nhật quy hoạch động. Khoảng cách ngắn nhất từ $i$ đến $j$ được cập nhật bằng giá trị nhỏ nhất giữa khoảng cách hiện tại (đã tính toán không dùng các đỉnh trung gian lớn hơn k-1) và khoảng cách nếu đi từ $i$ đến k rồi từ k đến $j$ (sử dụng các đường đi đã được tính toán chỉ dùng đỉnh trung gian nhỏ hơn k).
In kết quả: Sau khi ba vòng lặp hoàn thành, ma trận dist chứa khoảng cách ngắn nhất giữa mọi cặp đỉnh. Code in ra ma trận này, hiển thị "INF" cho các cặp đỉnh không có đường đi.
main(): Khởi tạo hai ví dụ đồ thị dưới dạng ma trận kề (INF biểu thị không có cạnh) và gọi hàm floydWarshall cho mỗi đồ thị.

Ví Dụ 2: Truy Vết Đường Đi Ngắn Nhất

Đôi khi, chúng ta không chỉ cần khoảng cách mà còn cần biết đường đi cụ thể. Chúng ta có thể mở rộng thuật toán Floyd-Warshall bằng cách sử dụng thêm một ma trận next_node[V][V]. next_node[i][j] sẽ lưu trữ đỉnh tiếp theo trên đường đi ngắn nhất từ đỉnh $i$ đến đỉnh $j$.

#include <iostream>
#include <vector>
#include <algorithm>

const int INF = 1e9; // Biểu diễn vô cùng
const int NO_PATH = -1; // Biểu diễn không có đường đi ban đầu

void reconstructPath(int start_node, int end_node, const std::vector<std::vector<int>>& next_node) {
    if (next_node[start_node][end_node] == NO_PATH) {
        std::cout << "Khong co duong di";
        return;
    }

    int current_node = start_node;
    while (current_node != end_node) {
        std::cout << current_node << " -> ";
        current_node = next_node[current_node][end_node];
    }
    std::cout << end_node;
}

void floydWarshallWithPath(std::vector<std::vector<int>>& graph) {
    int V = graph.size();
    std::vector<std::vector<int>> dist = graph;
    std::vector<std::vector<int>> next_node(V, std::vector<int>(V));

    // Khởi tạo ma trận next_node
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (graph[i][j] != INF && i != j) {
                next_node[i][j] = j; // Nếu có cạnh trực tiếp, đỉnh tiếp theo là j
            } else {
                next_node[i][j] = NO_PATH; // Ban đầu không có đường đi hoặc i==j
            }
        }
    }

    // Bước 2: Lặp qua các đỉnh trung gian k
    for (int k = 0; k < V; ++k) {
        // Bước 2a: Lặp qua tất cả các đỉnh nguồn i
        for (int i = 0; i < V; ++i) {
            // Bước 2b: Lặp qua tất cả các đỉnh đích j
            for (int j = 0; j < V; ++j) {
                 // Nếu đỉnh i hoặc đỉnh j không thể đạt được từ/đến đỉnh trung gian k, bỏ qua
                if (dist[i][k] == INF || dist[k][j] == INF) {
                    continue; // Tránh tràn số và chỉ xem xét đường đi hợp lệ qua k
                }

                // Cập nhật khoảng cách và thông tin đỉnh tiếp theo nếu đường đi qua k ngắn hơn
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next_node[i][j] = next_node[i][k]; // Đỉnh tiếp theo từ i trên đường đi mới là đỉnh tiếp theo từ i đến k
                }
            }
        }
    }

    // In ma trận khoảng cách cuối cùng (giống ví dụ 1)
    std::cout << "Ma tran khoang cach ngan nhat giua moi cap dinh:\n";
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (dist[i][j] == INF) {
                std::cout << "INF ";
            } else {
                std::cout << dist[i][j] << "   ";
            }
        }
        std::cout << std::endl;
    }

    // In một vài đường đi mẫu
    std::cout << "\nDuong di ngan nhat (mot vai cap dinh):\n";
    reconstructPath(0, 3, next_node); std::cout << std::endl; // Path from 0 to 3 (Graph 1)
    reconstructPath(0, 4, next_node); std::cout << std::endl; // Path from 0 to 4 (Graph 2)
    reconstructPath(3, 2, next_node); std::cout << std::endl; // Path from 3 to 2 (Graph 2)
    reconstructPath(1, 2, next_node); std::cout << std::endl; // Path from 1 to 2 (Graph 2 - no path)

}

int main() {
    // Ví dụ đồ thị 1 (không có trọng số âm)
    std::cout << "--- Do thi 1 (co truy vet duong di) ---\n";
    std::vector<std::vector<int>> graph1 = {
        {0,   5,  INF, 10},
        {INF, 0,   3,  INF},
        {INF, INF, 0,   1},
        {INF, INF, INF, 0}
    }; // Kích thước V=4
    floydWarshallWithPath(graph1);
    std::cout << std::endl;

    // Ví dụ đồ thị 2 (có trọng số âm, không có chu trình âm)
    std::cout << "--- Do thi 2 (co truy vet duong di) ---\n";
     std::vector<std::vector<int>> graph2 = {
        {0,   3,  8,   INF, -4},
        {INF, 0,  INF, 1,   7},
        {INF, 4,  0,   INF, INF},
        {2,   INF, -5,  0,   INF},
        {INF, INF, INF, 6,   0}
    }; // Kích thước V=5
    floydWarshallWithPath(graph2);

    return 0;
}

Giải thích Code Ví Dụ 2:

const int NO_PATH = -1;: Sử dụng một giá trị đặc biệt để đánh dấu ban đầu không có đường đi trực tiếp (hoặc đường đi chưa được xác định).
std::vector<std::vector<int>> next_node(V, std::vector<int>(V));: Khai báo ma trận next_node cùng kích thước với ma trận khoảng cách.
Khởi tạo next_node:
- Nếu có cạnh trực tiếp từ $i$ đến $j$ (graph[i][j] != INF và $i \neq j$), đỉnh tiếp theo trên đường đi trực tiếp này hiển nhiên là $j$. Ta gán next_node[i][j] = j.
- Trường hợp còn lại (không có cạnh trực tiếp hoặc $i=j$), ta gán next_node[i][j] = NO_PATH.
Cập nhật trong vòng lặp: Khi chúng ta tìm thấy một đường đi ngắn hơn từ $i$ đến $j$ thông qua đỉnh trung gian $k$ (dist[i][k] + dist[k][j] < dist[i][j]), chúng ta cập nhật dist[i][j]. Đồng thời, đỉnh tiếp theo từ $i$ trên đường đi ngắn nhất mới này sẽ là đỉnh tiếp theo từ $i$ trên đường đi ngắn nhất đã tìm được từ $i$ đến $k$. Do đó, chúng ta gán next_node[i][j] = next_node[i][k].
Hàm reconstructPath(start_node, end_node, next_node): Hàm này sử dụng ma trận next_node để in ra đường đi từ đỉnh start_node đến đỉnh end_node.
- Nó bắt đầu từ start_node.
- Ở mỗi bước, nó in ra đỉnh hiện tại và di chuyển đến đỉnh tiếp theo được chỉ định bởi next_node[current_node][end_node] cho đến khi đạt đến end_node.
- Nếu next_node[start_node][end_node] là NO_PATH ban đầu (tức là khoảng cách cuối cùng vẫn là INF), điều đó có nghĩa là không có đường đi giữa hai đỉnh này.
main(): Giống ví dụ 1, sử dụng các đồ thị mẫu và gọi hàm floydWarshallWithPath. Sau khi hàm chạy xong, gọi reconstructPath cho một vài cặp đỉnh để minh họa.

Ví Dụ 3: Phát Hiện Chu Trình Âm

Floyd-Warshall có một đặc điểm hữu ích là có thể phát hiện sự tồn tại của chu trình âm. Nếu sau khi thuật toán hoàn thành, khoảng cách ngắn nhất từ một đỉnh đến chính nó (dist[i][i]) là một số âm, điều đó chỉ ra rằng có một chu trình âm có thể đạt được từ đỉnh đó hoặc đạt tới đỉnh đó.

#include <iostream>
#include <vector>
#include <algorithm>

const int INF = 1e9; // Biểu diễn vô cùng

void floydWarshallWithNegativeCycleCheck(std::vector<std::vector<int>>& graph) {
    int V = graph.size();
    std::vector<std::vector<int>> dist = graph;

    // Bước 1 & 2: Tính toán ma trận khoảng cách (giống ví dụ 1)
    for (int k = 0; k < V; ++k) {
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                 if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // Bước 3: Kiểm tra chu trình âm
    bool hasNegativeCycle = false;
    for (int i = 0; i < V; ++i) {
        if (dist[i][i] < 0) {
            hasNegativeCycle = true;
            break; // Chỉ cần tìm một chu trình âm
        }
    }

    if (hasNegativeCycle) {
        std::cout << "Do thi chua chu trinh am.\n";
        // Trong trường hợp có chu trình âm, ma trận khoảng cách có thể không có ý nghĩa
        // cho các cặp đỉnh liên quan đến chu trình âm đó.
    } else {
        std::cout << "Do thi khong chua chu trinh am.\n";
        // In ma trận khoảng cách cuối cùng (nếu không có chu trình âm)
        std::cout << "Ma tran khoang cach ngan nhat giua moi cap dinh:\n";
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (dist[i][j] == INF) {
                    std::cout << "INF ";
                } else {
                    std::cout << dist[i][j] << "   ";
                }
            }
            std::cout << std::endl;
        }
    }
}

int main() {
    // Ví dụ đồ thị 1 (không có chu trình âm)
    std::cout << "--- Do thi 1 (kiem tra chu trinh am) ---\n";
    std::vector<std::vector<int>> graph1 = {
        {0,   5,  INF, 10},
        {INF, 0,   3,  INF},
        {INF, INF, 0,   1},
        {INF, INF, INF, 0}
    }; // Kích thước V=4
    floydWarshallWithNegativeCycleCheck(graph1);
    std::cout << std::endl;

    // Ví dụ đồ thị 3 (có chu trình âm)
    // Chu trinh am: 1 -> 2 -> 1 voi tong trong so 4 + (-5) = -1
    std::cout << "--- Do thi 3 (co chu trinh am) ---\n";
     std::vector<std::vector<int>> graph3 = {
        {0,   3,  8,   INF, -4},
        {INF, 0,  INF, 1,   7},
        {INF, 4,  0,   INF, INF},
        {2,   INF, -5,  0,   INF},
        {INF, INF, INF, 6,   0}
    }; // Kích thước V=5
    // Thay doi graph3 de co chu trinh am 1->2->1
    graph3[1][2] = 4; // Edge 1 -> 2 with weight 4
    graph3[2][1] = -5; // Edge 2 -> 1 with weight -5. Cycle 1->2->1 has weight -1

    floydWarshallWithNegativeCycleCheck(graph3);

    return 0;
}

Giải thích Code Ví Dụ 3:

Bước 1 & 2: Phần tính toán ma trận khoảng cách hoàn toàn giống với Ví dụ 1. Thuật toán vẫn chạy ngay cả khi có chu trình âm.
Bước 3: Kiểm tra chu trình âm: Sau khi ba vòng lặp chính hoàn thành, ta duyệt qua đường chéo chính của ma trận dist (dist[i][i]).
- for (int i = 0; i < V; ++i): Duyệt qua mỗi đỉnh i.
- if (dist[i][i] < 0): Nếu khoảng cách ngắn nhất từ đỉnh i đến chính nó là âm, điều này chỉ ra rằng có một đường đi từ i đến i với tổng trọng số âm. Đường đi này phải đi qua một chu trình âm. Do đó, ta phát hiện chu trình âm và đặt cờ hasNegativeCycle = true.
Kết quả: Nếu hasNegativeCycle là true, ta in ra thông báo đồ thị chứa chu trình âm. Nếu không, ta in ra ma trận khoảng cách ngắn nhất (vì trong trường hợp không có chu trình âm, kết quả của thuật toán là chính xác).

Ưu và Nhược điểm của Floyd-Warshall

Ưu điểm:

Đơn giản để triển khai: Chỉ cần ba vòng lặp lồng nhau đơn giản.
Giải quyết APSP: Tìm đường đi ngắn nhất cho mọi cặp đỉnh cùng một lúc.
Hỗ trợ trọng số âm: Xử lý đồ thị có trọng số âm (miễn là không có chu trình âm).
Phát hiện chu trình âm: Có khả năng phát hiện sự tồn tại của chu trình âm.
Hiệu quả cho đồ thị dày đặc: Đối với đồ thị dày đặc ($|E| \approx |V|^2$), độ phức tạp $O(V^3)$ là cạnh tranh hoặc tốt hơn so với chạy Dijkstra $|V|$ lần.

Nhược điểm:

Độ phức tạp thời gian cao: $O(V^3)$ có thể quá chậm đối với đồ thị rất lớn. Đối với đồ thị thưa ($|E| \ll |V|^2$), chạy Dijkstra $|V|$ lần ($O(|V||E|\log|V|)$) thường nhanh hơn.
Độ phức tạp không gian: $O(V^2)$ có thể tốn bộ nhớ đối với đồ thị rất lớn.
Không hiệu quả cho SSSP: Nếu chỉ cần tìm đường đi ngắn nhất từ một đỉnh nguồn duy nhất, Bellman-Ford hoặc Dijkstra sẽ phù hợp hơn.

Bài tập ví dụ:

Đường đi ngắn nhất I

Trong một vụ án phức tạp, FullHouse Dev được một luật sư thuê để giải quyết một bài toán về tìm đường đi ngắn nhất giữa các thành phố.

Bài toán

Có $n$ thành phố và $m$ đường bay kết nối giữa chúng. Nhiệm vụ của FullHouse Dev là xác định độ dài đường đi ngắn nhất từ thành phố Syrjälä đến mọi thành phố khác. Các thành phố được đánh số từ $1$ đến $n$, trong đó Syrjälä là thành phố số $1$.

INPUT FORMAT:

Dòng đầu tiên chứa hai số nguyên $n$ và $m$: số lượng thành phố và số đường bay.
$m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a$, $b$ và $c$: đường bay bắt đầu từ thành phố $a$, kết thúc tại thành phố $b$, và có độ dài $c$. Mỗi đường bay là một chiều.
Có thể đảm bảo rằng luôn có thể đi từ Syrjälä đến tất cả các thành phố khác.

OUTPUT FORMAT:

In ra $n$ số nguyên: độ dài đường đi ngắn nhất từ Syrjälä đến các thành phố $1,2,\dots,n$.

Ràng buộc:

$1 \leq n \leq 10^5$
$1 \leq m \leq 2 \cdot 10^5$
$1 \leq a,b \leq n$
$1 \leq c \leq 10^9$

Ví dụ

INPUT

OUTPUT

0 5 2

Giải thích

Độ dài đường đi ngắn nhất từ thành phố 1 (Syrjälä) đến chính nó là 0
Độ dài đường đi ngắn nhất đến thành phố 2 là 5 (đi từ 1 → 3 → 2)
Độ dài đường đi ngắn nhất đến thành phố 3 là 2 (đi trực tiếp từ 1 → 3) Đây là bài toán tìm đường đi ngắn nhất từ một đỉnh nguồn duy nhất (thành phố 1) đến tất cả các đỉnh khác trong đồ thị có hướng với trọng số không âm.

Hướng giải:

Nhận diện bài toán: Đây là bài toán Single-Source Shortest Path (SSSP) trên đồ thị có hướng, trọng số cạnh không âm.
Lựa chọn thuật toán: Thuật toán Dijkstra là thuật toán phù hợp và hiệu quả nhất cho bài toán SSSP với trọng số không âm.
Cấu trúc dữ liệu:
- Sử dụng danh sách kề (adjacency list) để biểu diễn đồ thị, lưu trữ các cạnh đi ra từ mỗi đỉnh cùng với trọng số của chúng.
- Sử dụng một mảng để lưu trữ khoảng cách ngắn nhất tạm thời từ đỉnh nguồn đến mỗi đỉnh. Ban đầu, khoảng cách đến đỉnh nguồn là 0, các đỉnh khác là vô cùng lớn.
- Sử dụng một hàng đợi ưu tiên (priority queue) để lưu trữ các cặp {khoảng cách, đỉnh}, giúp luôn chọn ra đỉnh có khoảng cách tạm thời nhỏ nhất chưa được "chốt" khoảng cách cuối cùng.
Các bước thực hiện thuật toán Dijkstra:
- Khởi tạo mảng khoảng cách dist với dist[1] = 0 và dist[i] = vô cùng lớn cho i > 1.
- Đưa cặp {0, 1} (khoảng cách, đỉnh) vào hàng đợi ưu tiên.
- Trong khi hàng đợi ưu tiên chưa rỗng:
  - Lấy cặp {d, u} có khoảng cách d nhỏ nhất từ hàng đợi.
  - Nếu d lớn hơn dist[u] hiện tại, bỏ qua (đây là một phiên bản cũ hơn của đỉnh u với khoảng cách lớn hơn).
  - Duyệt qua tất cả các đỉnh v kề với u (qua cạnh u -> v có trọng số w):
    - Nếu dist[u] + w < dist[v]:
      - Cập nhật dist[v] = dist[u] + w.
      - Đưa cặp {dist[v], v} vào hàng đợi ưu tiên.
- Sau khi vòng lặp kết thúc, mảng dist sẽ chứa độ dài đường đi ngắn nhất từ đỉnh 1 đến tất cả các đỉnh còn lại.
Lưu ý: Do trọng số cạnh có thể lớn (lên tới 10^9) và số lượng cạnh/đỉnh có thể nhiều, tổng khoảng cách có thể vượt quá giới hạn của kiểu int 32-bit. Nên sử dụng kiểu dữ liệu long long cho mảng khoảng cách.

Cuối cùng, in ra các giá trị trong mảng dist từ dist[1] đến dist[n].

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.