let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Thuật toán Floyd - Tìm đường đi ngắn nhất giữa mọi cặp đỉnh

Thuật toán Floyd - Tìm đường đi ngắn nhất giữa mọi cặp đỉnh

Contents

Floyd hay còn gọi là Floyd-Warshall là thuật toán để tìm đường đi ngắn nhất giữa mọi cặp đỉnh. Floyd hoạt động được trên đồ thị có hướng, có thể có trọng số âm, tuy nhiên không có chu trình âm. Ngoài ra, Floyd còn có thể được dùng để phát hiện chu trình âm.

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

Gọi \(C\) là ma trận kề của đồ thị và \(D[u][v]\) là độ dài đường đi ngắn nhất từ \(u\) đến \(v\).

Ban đầu ta khởi tạo \(D\) như sau:

  • \(D[u][u] = 0\) với mọi đỉnh \(u\)
  • \(D[u][v] = C[u][v]\) nếu có cạnh nối từ \(u\) đến \(v\), ngược lại \(D[u][v] = \infty\)

Sau khi đã khởi tạo, ta tính D như sau:

for k:=1 to n do
    for i:=1 to n do
        for j:=1 to n do
            if D[i][j] > D[i][k] + D[j][k] then
                D[i][j] = D[i][k] + D[j][k];

Ý nghĩa của đoạn code trên rất đơn giản, lần lượt duyệt tất cả các cặp \((k,i,j)\), nếu đường hiện tại từ \(i\) đến \(j\) dài hơn đường đi từ \(i\) qua \(k\) rồi từ \(k\) qua \(j\) thì ta cập nhật lại \(D[i][j]\) bằng đường đi qua trung gian \(k\) này.

Lưu ý là ta phải duyệt \(k\) trước \(i\) và \(j\) thì thuật toán mới chạy đúng.

Truy vết đường đi

Để truy vết đường đi, ta thêm một mảng \(T\) với ý nghĩa \(T[u][v]\) là đỉnh kề với đỉnh \(u\) trên đường đi ngắn nhất từ \(u\) đến \(v\).

Khởi tạo T như sau:

  • \(T[u][v] = v\) nếu có cạnh nối từ \(u\) đến \(v\)

Sau đó ta kết hợp tính \(T\) trong quá trình tính \(D\):

for k:=1 to n do
    for i:=1 to n do
        for j:=1 to n do
            if D[i][j] > D[i][k] + D[j][k] then
                D[i][j] = D[i][k] + D[j][k];
                T[i][j] = T[i][k];

Đoạn code sau trả về danh sách các đỉnh trên đường đi ngắn nhất từ \(u\) đến \(v\):

vector<int> trace(int u, int v) {
    vector<int> path;
    do {
        path.push_back[u];
        u = T[u][v];
    } while (pack.back() != v);
    return path;
}

Cài đặt

Phần sau là code giải bài FLOYD sử dụng thuật toán Floyd.

#include <iostream>
#include <vector>
using namespace std;

#define rep(i,a,b) for (int i=a; i<=b; i++)
#define N 101
int C[N][N];
int T[N][N];

vector<int> trace(int u, int v) {
    vector<int> path;
    do {
        path.push_back(u);
        u = T[u][v];
    } while (path.back() != v);
    return path;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    rep(i,1,N) rep(j,1,N) C[i][j] = 1e9;
    rep(i,1,N) C[i][i] = 0;

    int n, m, q;
    cin >> n >> m >> q;
    rep(_,1,m) {
        int u, v, w;
        cin >> u >> v >> w;
        C[u][v] = C[v][u] = w;
        T[u][v] = v;
        T[v][u] = u;
    }

    rep(k,1,n) rep(i,1,n) rep(j,1,n) {
        if (C[i][j] > C[i][k] + C[k][j]) {
            C[i][j] = C[i][k] + C[k][j];
            T[i][j] = T[i][k];
        }
    }

    rep(_,1,q) {
        int k,u,v;
        cin >> k >> u >> v;
        if (k) {
            auto path = trace(u,v);
            cout << path.size() << ' ';
            for (int u: path) cout << u << ' ';
        } else cout << C[u][v];
        cout << '\n';
    }
}

Phát hiện chu trình âm

Floyd có thể dùng để phát hiện chu trình âm. Sau khi chạy thuật toán, nếu \(D[u][u] < 0\) thì có chu trình âm đi qua đỉnh \(u\)

Liệt kê tất cả đường đi đơn

Floyd còn có thể được dùng để liệt kê tất cả các đường đi đơn (mỗi đỉnh đi qua nhiều nhất một lần). Ý tưởng như sau:

  • Kí hiệu (a, b, c) là một đường đi bắt đầu từ a, đi qua b rồi đến c.
  • Gọi paths[u][v] là danh sách tất cả các đường đi từ đỉnh u đến đỉnh v.
  • Ban đầu, nếu u và v không có cạnh nối thì paths[u][v] là danh sách rỗng, ngược lại ta thêm một đường đi trực tiếp từ u đến v vào danh sách này. Vậy, nếu u và v có cạnh nối thì paths[u][v] = [(u, v)].
  • Duyệt 3 vòng for (k, i, j) như trong Floyd bình thường.
    • Đến đây, ta thấy kết hợp paths[i][k] và paths[k][j] lại sẽ cho ta thêm những đường đi từ i đến j, qua trung gian là k.
    • Cần chú ý kiểm tra xem 2 đường đi có đỉnh trùng không trước khi kết hợp chúng.

Cụ thể, cài đặt trong Python 3 như sau:

from itertools import product

# Test bằng đồ thị này, không cần nhập file
# Đây là danh sách cạnh, đồ thị có hướng
graph = [
6,      # 6 đỉnh
(0, 1), # cạnh từ 0 đi đến 1
(0, 2),
(1, 3),
(1, 4),
(2, 1),
(2, 5),
(3, 5),
(4, 3),
]

class Graph:
    def __init__(self, graph):
        n = graph[0]
        # Khởi tạo mảng 2 chiều, mỗi phần tử là 1 danh sách các đường đi
        # paths[u][v] là danh sách các đường đi từ u đến v
        paths = [[[] for j in range(n)] for i in range(n)]
        # Ban đầu, nếu 2 đỉnh có cạnh nối trực tiếp thì
        # thì thêm vào danh sách đường đi
        for u, v in graph[1:]:
            paths[u][v].append((u, v))
        # Dùng Floyd để sinh tất cả các đường đi giữa mọi cặp đỉnh
        for k, i, j in product(range(n), repeat=3):
            for u, v in product(paths[i][k], paths[k][j]):
                # Dùng set để truy vấn nhanh hơn
                x = set(u)
                # Nếu 2 đường u và v không có cạnh chung thì
                # thêm 1 đường mới là u + v
                if all(y not in x for y in v[1:]):
                    paths[i][j].append(u + v[1:])

        self.n = n
        self.paths = paths

if __name__ == "__main__":
    g = Graph(graph)
    print("Các đường đi từ đỉnh 0 đến đỉnh 5")
    for path in g.paths[0][5]:
        print(path)

Cá nhân mình thích cách làm này hơn duyệt đệ quy quay lui vì nó đẹp hơn, nhất là khi cài bằng Python.

Kĩ thuật này đã được sử dụng trong https://github.com/juchiast/a3c.

Comments