Đồ thị (Graph) Phần 6: Các thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số (Phần 2) – Floyd-Warshall

Đỗ Thị Hồng Ngát 25/10/2023
25
Th10

Bên cạnh Dijkstra, Floyd-Warshall cũng là một thuật toán về tìm đường đi ngắn nhất trên đồ thị có trọng số cần biết để phục vụ cho các kỳ thi liên quan tới lập trình thi đấu. Tư tưởng của thuật toán này có thể tóm tắt như sau: xét mọi cặp đỉnh \((u, v)\), nếu đường đi ngắn nhất đang ghi nhận từ \(u\) đến \(k\) cộng với đường đi ngắn nhất đang ghi nhận từ \(u\) đến \(v\) (\(k\) là 1 đỉnh bất kỳ trong đồ thị) nhỏ hơn đường đi ngắn nhất từ \(u\) đến \(v\) đã tính từ trước đó, thì đó sẽ là đường đi ngắn nhất từ \(u\) đến \(v\) hiện tại.

1. Bài toán 1

Cho đơn đồ thị vô hướng \(N\) đỉnh, \(M\) cạnh, trọng số các cạnh đều là nguyên dương.

Có 2 loại câu hỏi:

  • \(0\) \(u\) \(v\): Cho biết đường đi ngắn nhất từ \(u\) tới \(v\) là bao nhiêu.
  • \(1\) \(u\) \(v\): Hãy chỉ ra đường đi ngắn nhất từ \(u\) \(→\) \(v\).

Bài cơ bản này nhằm kiểm tra kỹ năng xây dựng các module chương trình con dành cho truy vết cách hợp lý, sử dụng nhuần nhuyễn chương trình con, lời gọi hàm.

Nguồn bài: Floyd hoặc Dijkstra (cơ bản) – VNOI
Input:

  • Dòng 1: Ba số nguyên \(N, M, K\). \((1 ≤ N ≤ 100, 1 ≤ M ≤ frac{N(N – 1)}{2}, 1 ≤ K ≤ 1000)\).
  • \(M\) dòng tiếp theo, dòng thứ \(i\) gồm 3 số nguyên dương \(u, v, c\) cho biết cạnh \((u, v)\) có trọng số là \(c\) \((1 ≤ c ≤ 10000).\)
  • \(K\) dòng tiếp theo là \(K\) câu hỏi, dòng thứ \(j\) sẽ có định dạng như đã nêu ở trên.

Output:

  • Ứng với mỗi câu hỏi trong \(K\) câu hỏi thì ta phải trả lời mỗi dòng như sau:
  • Câu hỏi \(0\) \(u\) \(v\): Ghi ra 1 số nguyên duy nhất là độ dài đường đi ngắn nhất từ \(u\) \(→\) \(v\).
  • Câu hỏi \(1\) \(u\) \(v\): Ghi ra số đầu tiên là số \(X\) là số đỉnh trên đường đi ngắn nhất này, tiếp đó ghi ra \(X\) số là chỉ số các đỉnh theo thứ tự xuất hiện trên hành trình.

Sample Input

3 3 2
1 2 3
2 3 1
1 3 5
0 1 2
1 1 3

Sample Output

3
1 2 3

 

Phân tích bài toán:

  • Nhận xét: Do \(N\) tương đối nhỏ cùng với nhiều truy vấn, ta nghĩ tới việc sử dụng thuật toán Floyd-Warshall để giải quyết bài toán này.
  • Trước hết, ta cần khởi tạo mảng \(d\) 2 chiều với \(d[u][v]\) là đường đi ngắn nhất đang được ghi nhận từ \(u\) tới \(v\).
  • Do đó, ta sẽ khởi tạo \(d[u][v] = c[u][v]\) nếu tồn tại cạnh nối giữa cặp \(u – v\). Ngược lại, ta sẽ khởi tạo \(d[u][v] = +∞\) với \(u\) khác \(v\).

Ta có mã giả của thuật toán Floyd-Warshall như sau:

for (k = 1, k -> n; k++)
    for (u = 1; u -> n; u++)
        for (v = 1; v -> n; v++) 
            d[u][v] = min(d[u][v], d[u][k] + d[v][k])

Mô tả thuật toán:

Giá trị của \(d[u][v]\) ban đầu được hình dung như sau:

\(u/v\) \(1\) \(2\) \(3\)
\(1\) \(0\) \(3\) \(5\)
\(2\) \(3\) \(0\) \(1\)
\(3\) \(5\) \(1\) \(0\)
  • Tiếp theo, chọn lần lượt các đỉnh trung gian \(k\). Tiếp theo, chọn lần lượt 2 đỉnh \(u – v\) và ta sẽ dẫn tới nhận xét như sau: Đường đi \(u – v\) ngắn nhất tính tới hiện thời chính \(min\) của đường đi \(u – v\) ngắn nhất tới thời điểm đang xét với \(d[u][k] + d[k][v]\).
  • Nếu \(k = 1\), bảng giá trị \(d[u][v]\) sẽ trở thành như sau:
\(u/v\) \(1\) \(2\) \(3\)
\(1\) \(0\) \(3\) \(5\)
\(2\) \(3\) \(0\) \(1\)
\(3\) \(5\) \(1\) \(0\)
  • Nếu \(k = 2\), bảng giá trị \(d[u][v]\) sẽ trở thành như sau:
\(u/v\) \(1\) \(2\) \(3\)
\(1\) \(0\) \(3\) \(4\)
\(2\) \(3\) \(0\) \(1\)
\(3\) \(4\) \(1\) \(0\)
  • Nếu \(k = 3\), bảng giá trị \(d[u][v]\) sẽ trở thành như sau:
\(u/v\) \(1\) \(2\) \(3\)
\(1\) \(0\) \(3\) \(4\)
\(2\) \(3\) \(0\) \(1\)
\(3\) \(4\) \(1\) \(0\)

→ Vậy đường đi ngắn nhất từ 1 → 2 là 3.

Để truy vết, ta sẽ làm như sau:

  • Gọi \(trace[u][v]\) với ý nghĩa: đó là đỉnh kề với đỉnh \(u\) trong đường đi ngắn nhất từ \(u\) đến \(v\).
  • Khởi tạo: Với mọi cặp cạnh \(u – v\) tồn tại trên đồ thị, ta gán: \(trace[u][v] = v\), \(trace[v][u] = u\).
  • Vậy, thứ tự các đỉnh nằm trên đường đi ngắn nhất từ \(u\) tới \(v\) được biểu diễn như sau:
    • \(u → p1 = trace[u][v] → p2 = trace[p1][v] → … → v\).

Code mẫu:

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define inf 1e18

const int N = 1e2 + 5;

int trace[N][N], d[N][N];

int n, m;

void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int u = 1; u <= n; u++) {
            for (int v = 1; v <= n; v++) {
                if (d[u][v] > d[u][k] + d[k][v]) {
                    d[u][v] = d[u][k] + d[k][v];
                    trace[u][v] = trace[u][k];
                }
            }
        }
    }
}

void findPath(int u, int v) {
    vector<int> pth;
    while (true) {
        pth.push_back(u);
        if (u == v) {
            break;
        }
        u = trace[u][v];
    }
    cout << pth.size() << " ";
    for (auto x : pth) {
        cout << x << " ";
    }
}

int k;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j)
                d[i][j] = inf;
        }
    }
    for (int i = 1; i <= m; i++) {
        int u, v, c; cin >> u >> v >> c;
        d[u][v] = d[v][u] = c;
        trace[u][v] = v;
        trace[v][u] = u;
    }
    floyd();
    for (int _ = 1; _ <= k; _++) {
        int type, u, v; cin >> type >> u >> v;
        if (type == 1) {
            findPath(u, v);
        }
        else if (type == 0) {
            cout << d[u][v];
        }
        cout << 'n';
    }
    return 0;
}

 

→ Độ phức tạp thời gian: \(O(V^3)\) với \(V\) là số đỉnh của đồ thị.

2. Bài toán 2:

Nguồn bài: Greg and Graph – Codeforces

Lưu ý: giới hạn thời gian của bài này là 3s

Tóm tắt đề bài:

Cho đồ thị có hướng, có trọng số gồm \(n\) đỉnh. Bạn có một trò chơi gồm \(n\) bước, mỗi bước bao gồm xóa một đỉnh \(x\) theo yêu cầu.

Với mỗi bước, hãy tìm \(∑_{v, u, v≠u} d(i, v, u)\).

Quy ước: \(d(i, v, u)\) là đường đi ngắn nhất từ đỉnh v đến đỉnh u trước khi xóa \(x_i\). Những đỉnh \(x_i\) đã bị xóa cũng đồng nghĩa với việc những cạnh đi vào hay đi ra từ nó cũng bị xóa theo.

Input

  • Dòng đầu tiên chứa số nguyên dương \(n\) \((1 ≤ n ≤ 500).\)
  • \(n\) dòng tiếp theo biểu diễn ma trận kề của đồ thị: coi số thứ \(j\) ở hàng thứ \(i\) là \(a_{ij}\) \((a_{ij} ≤ 100000)\), biểu diễn trọng số của cạnh được nối từ đỉnh \(i\) tới đỉnh \(j\).
  • Dòng cuối cùng chứa \(n\) số nguyên dương: \(x_1, x_2, x_3…x_n\) lần lượt thể hiện những đỉnh mà bạn xóa theo từng bước.

Output

  • In ra \(n\) số nguyên dương, số thứ \(i\) biểu diễn giá trị thỏa mãn đề bài trước khi thực hiện bước thứ \(i\).

Sample Input

4
0 3 1 1
6 0 400 1
2 4 0 1
1 1 1 0
4 1 2 3

Sample Output

17 23 404 0

Phân tích bài toán:

  • Bài toán này có giới hạn \(n\) tương đối nhỏ cùng với việc giá trị \(v\) bắt đầu không thật sự chỉ cố định ở 1 vị trí, ta có thể liên tưởng tới thuật toán Floyd-Warshall để giải quyết bài này.
  • Để có thể tìm được đường đi trước mỗi truy vấn mà đảm bảo không tồn tại những cạnh đi vào từ \(x\) hay đi ra từ \(x\), ta nghĩ tới việc lưu các query theo thứ tự từ \(n\) về \(1\) và chuyển yêu cầu bài toán như sau: Cho các số \(x_{1}, x_{2}, x_{3}…, x_{n}\), với mỗi \(x_{i}\) thể hiện ta sẽ thêm đỉnh \(x_{i}\) vào đồ thị, tìm \(∑_{v, u, v≠u} d(i, v, u)\) với \(d(i, v, u)\) có nghĩa là đường đi ngắn nhất từ đỉnh \(v\) tới đỉnh \(u\) sau mỗi truy vấn \(i\). Từ đây, bài toán đã trở nên dễ dàng giải quyết hơn rất nhiều.
  • Ta có công thức quy hoạch động như sau: \(d(i, v, u) = min(d(i, v, u),\) \(d(i, v, k) + d(i, k, u))\) với đỉnh \(v, u, k\) đã tồn tại trên đồ thị và \(k = x[i]\). Đáp số của bài toán chính là: \(∑_{v, u, v≠u} d(n, v, u)\), \(∑_{v, u, v≠u} d(n – 1, v, u)\)\(,…,\)\(∑_{v, u, v≠u} d(1, v, u)\).

Code mẫu:

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define inf 1e18

const int N = 5e2 + 5;

int d[N][N], query[N], ans[N], n;

bool ok[N];

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> d[i][j];
        }
    }
    memset(ok, false, sizeof ok);
    // chưa có đỉnh nào được chọn
    for (int i = n; i >= 1; i--) {
        cin >> query[i];
        // lưu truy vấn theo thứ tự ngược lại
    }  
    for (int _ = 1; _ <= n; _++) {
        int k = query[_];
        ok[k] = true;
        ans[_] = 0;
        for (int u = 1; u <= n; u++) {
            for (int v = 1; v <= n; v++) {
                d[u][v] = min(d[u][v], d[u][k] + d[k][v]);
                if (ok[u] == true && ok[v] == true) {
                    ans[_] += d[u][v];
                    // nếu như (u, v) đã được thêm vào 
                    // thì mới tồn tại d(i, u, v) thỏa mãn
                }
            }
        }
    }
    for (int i = n; i >= 1; i--) {
        cout << ans[i] << " ";
    }
    return 0;
}

3. Khi nào sử dụng thuật toán Floyd-Warshall?

  • Thuật toán Floyd-Warshall thường được sử dụng để giải quyết những bài toán liên quan tới đường đi ngắn nhất giữa một hay nhiều cặp đỉnh với trọng số nhỏ. Đặc biệt, khác với Dijkstra, thuật toán này cho phép xử lý những bài toán liên quan tới trọng số âm.
  • Qua 2 bài toán trên, dễ dàng thấy nhất thuật toán Floyd-Warshall là một công cụ rất mạnh nếu như số đỉnh của đồ thị nhỏ (với 1s, giới hạn của \(n\) thường rơi vào khoảng 400) do tính đa dụng của nó, đặc biệt với những bài toán không cố định vị trí bắt đầu.
  • Thế nhưng, do độ phức tạp của thuật toán này tương đối lớn so với Dijkstra, nên những bài yêu cầu giới hạn \(n\) lớn chính là nhược điểm của thuật toán này. Chính vì vậy, cần đọc kỹ dữ kiện cũng như yêu cầu đề cho để có thể cân nhắc xem liệu có nên sử dụng thuật toán này hay không.

4. Luyện tập

Đây là một số bài tập luyện tập trong sách Competitive Programming Advanced của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn

Unable to display PDF file. Download instead.

Áp dụng giải bài RDBUILD

Phân tích bài toán

  • Bây giờ mình sẽ giả sử 4 thành phố đặc biệt có ký hiệu lần lượt là \(x_{1}, x_{2}, x_{3}, x_{4}\), và \(d[u][v]\) là chi phí ít nhất để xây dựng các con đường từ \(u\) tới \(v\). Do luôn tồn tại ít nhất 1 phương án xây dựng sao cho 4 thành phố đặc biệt liên thông nên ta có nhận xét như sau: chi phí ít nhất để xây dựng các con đường thỏa mãn đề bài chính là: \(min(d[x_{1}][u] + d[x_{2}][u] + d[u][v] + d[v][x_{3}] + d[v][x_{4}])\) với mọi cặp cạnh \(u – v\) trên đồ thị, và với mọi hoán vị của \(x_{1}, x_{2}, x_{3}, x_{4}\).
  • Qua nhận xét trên, cộng với việc dữ kiện của đề bài tương đối nhỏ \((n ≤ 100)\) nên cách giải tối ưu nhất cho bài này chính là sử dụng thuật toán Floyd-Warshall (do ta phải tìm cách xây dựng đường có chi phí nhỏ nhất giữa mọi cặp cạnh \(u – v\)).

Code mẫu:

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define inf 1e18

const int N = 1e2 + 5;

int d[N][N], city[4], n;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < 4; i++) cin >> city[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j) {
                d[i][j] = inf;
            }
        }
    }
    for (int u, v, c; cin >> u >> v >> c; ) {
        d[u][v] = c;
        d[v][u] = c;
    }
    for (int k = 1; k <= n; k++) {
        for (int u = 1; u <= n; u++) {
            for (int v = 1; v <= n; v++) {
                d[u][v] = min(d[u][v], d[u][k] + d[k][v]);
            }
        }
    }
    int res = inf;
    do {
        for (int u = 1; u <= n; u++) {
            for (int v = 1; v <= n; v++) {
                res = min(res, d[u][city[0]] + d[u][city[1]] + d[u][v] + d[v][city[2]] + d[v][city[3]]);
            }
        }
    } while (next_permutation(city, city + 4));
    cout << res;
    return 0;
}

Bài viết liên quan:

Bài viết cùng chủ đề:

Đỗ Thị Hồng Ngát

Để lại một bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *