Skip to content

Bài 23: Floyd-Warshall & Bellman-Ford

Tác giả: FPTOJ Team
Nội dung tham khảo từ: VNOI Wiki - Các thuật toán về tìm đường đi ngắn nhất

1. Bellman-Ford — Đường đi ngắn nhất có trọng số âm

Bản chất vấn đề

Cho đồ thị có hướng \(G = (V, E)\) với \(|V| = n\) đỉnh, \(|E| = m\) cạnh, mỗi cạnh có trọng số \(w(u,v)\) có thể âm. Cho đỉnh nguồn \(s\). Tìm đường đi ngắn nhất từ \(s\) đến mọi đỉnh \(v \in V\), hoặc phát hiện tồn tại chu trình âm (negative cycle).

Đây là mở rộng của bài toán đường đi ngắn nhất một nguồn (Single-Source Shortest Path — SSSP) mà Dijkstra không giải được khi có trọng số âm.

Tư duy cốt lõi

Vấn đề của Dijkstra với trọng số âm:

Dijkstra chọn đỉnh chưa thăm có \(dist\) nhỏ nhất rồi đánh dấu "xong". Nhưng khi có cạnh âm, một đỉnh đã đánh dấu có thể được cải thiện qua đường đi khác chứa cạnh âm → kết quả sai.

Ý tưởng Bellman-Ford — Thư giãn lặp:

Thay vì chọn đỉnh "tốt nhất", Bellman-Ford duyệt tất cả cạnh và cập nhật (thư giãn) nếu tìm được đường ngắn hơn. Lặp lại \(n - 1\) lần.

graph LR
    subgraph "Bellman-Ford: Thư giãn lặp"
        A["Khởi tạo dist[s] = 0, còn lại = ∞"] --> B["Lặp i = 1 .. n-1"]
        B --> C["Duyệt mọi cạnh (u, v, w)"]
        C --> D{"dist[u] + w < dist[v]?"}
        D -->|"Có"| E["dist[v] = dist[u] + w"]
        D -->|"Không"| F["Giữ nguyên"]
        E --> G{"Còn cạnh?"}
        F --> G
        G -->|"Có"| C
        G -->|"Hết"| H{"Lặp thêm lần nữa?"}
        H -->|"Có cạnh cập nhật"| I["Tồn tại chu trình âm!"]
        H -->|"Không"| J["Kết quả chính xác"]
    end

Thư giãn (Relaxation) là thao tác cốt lõi: kiểm tra xem đường đi từ \(s\) đến \(v\) qua \(u\) có ngắn hơn đường đi hiện tại hay không. Nếu có, cập nhật:

\[dist[v] \leftarrow dist[u] + w(u, v)\]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
bool bellmanFord(int n, int s, vector<tuple<int,int,int>>& edges,
                 vector<long long>& dist) {
    dist.assign(n + 1, LLONG_MAX);  // khởi tạo mảng dist
    dist[s] = 0;                     // khoảng cách từ nguồn đến chính nó

    for (int i = 1; i < n; i++) {   // lặp n-1 lần
        for (auto [u, v, w] : edges) {  // duyệt từng cạnh
            if (dist[u] != LLONG_MAX && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;  // thư giãn cạnh (u,v)
        }
    }

    for (auto [u, v, w] : edges) {  // kiểm tra chu trình âm
        if (dist[u] != LLONG_MAX && dist[u] + w < dist[v])
            return true;            // phát hiện chu trình âm
    }
    return false;                    // không có chu trình âm
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def bellman_ford(n, s, edges):
    dist = [float('inf')] * (n + 1)  # khởi tạo mảng dist
    dist[s] = 0                       # khoảng cách từ nguồn

    for _ in range(n - 1):            # lặp n-1 lần
        for u, v, w in edges:          # duyệt từng cạnh
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w  # thư giãn cạnh (u,v)

    for u, v, w in edges:              # kiểm tra chu trình âm
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return True, dist          # phát hiện chu trình âm
    return False, dist                 # không có chu trình âm

Phân tích tính đúng đắn

Vì sao lặp đúng \(n - 1\) lần?

Đường đi ngắn nhất trong đồ thị \(n\) đỉnh đi qua tối đa \(n - 1\) cạnh (nếu \(\geq n\) cạnh thì có chu trình, và chu trình âm sẽ bị phát hiện riêng).

Khi lặp lần thứ \(i\), Bellman-Ford đã tìm được đường đi ngắn nhất sử dụng tối đa \(i\) cạnh. Sau \(n - 1\) lần lặp, mọi đường đi ngắn nhất (tối đa \(n - 1\) cạnh) đều đã được tìm thấy.

Vì sao kiểm tra thêm lần thứ \(n\)?

Nếu sau \(n - 1\) lần lặp vẫn tồn tại cạnh \((u, v)\) sao cho \(dist[u] + w < dist[v]\), nghĩa là có đường đi sử dụng \(\geq n\) cạnh mà vẫn cải thiện được → đường đi này chứa chu trình âm → có thể ngắn mãi mãi.

Minh họa phát hiện chu trình âm:

Xét đồ thị 3 đỉnh với các cạnh có hướng:

Cạnh Trọng số
\(1 \to 2\) \(1\)
\(2 \to 3\) \(-1\)
\(3 \to 2\) \(-1\)

Biến động \(dist\) qua các lần lặp (khởi tạo từ đỉnh \(1\)):

Lặp \(dist[1]\) \(dist[2]\) \(dist[3]\) Cạnh cập nhật
Khởi tạo \(0\) \(\infty\) \(\infty\) —
1 \(0\) \(1\) \(0\) \(1 \to 2\), \(2 \to 3\)
2 \(0\) \(-1\) \(-2\) \(3 \to 2\), \(2 \to 3\)
Kiểm tra — \(-3\) — \(3 \to 2\) vẫn cải thiện → chu trình âm!

Đánh giá độ phức tạp

Yếu tố Độ phức tạp
Thời gian \(O(nm)\) — \(n - 1\) lần lặp, mỗi lần duyệt \(m\) cạnh
Không gian \(O(n + m)\) — mảng \(dist\) và danh sách cạnh

So sánh với Dijkstra:

  • Dijkstra: \(O(m \log n)\) với min-heap, nhưng không xử lý được trọng số âm.
  • Bellman-Ford: \(O(nm)\), chậm hơn, nhưng xử lý được trọng số âm và phát hiện chu trình âm.

2. Floyd-Warshall — Đường đi ngắn nhất mọi cặp

Bản chất vấn đề

Cho đồ thị \(G = (V, E)\) với \(n\) đỉnh, mỗi cạnh có trọng số \(w(u,v)\) (có thể âm, nhưng không có chu trình âm). Tìm đường đi ngắn nhất giữa mọi cặp đỉnh \((i, j)\).

Đây là bài toán All-Pairs Shortest Path (APSP). Nếu chạy Bellman-Ford từ mỗi đỉnh sẽ mất \(O(n^2 m)\), quá chậm. Floyd-Warshall giải quyết trong \(O(n^3)\).

Tư duy cốt lõi

Ý tưởng — Quy hoạch động 3 chiều:

Gọi \(dist[i][j]\) là độ dài đường đi ngắn nhất từ \(i\) đến \(j\). Floyd-Warshall duyệt qua các đỉnh trung gian \(k = 1, 2, \ldots, n\) và cập nhật:

\[dist[i][j] = \min(dist[i][j],\ dist[i][k] + dist[k][j])\]

Sau khi xử lý xong đỉnh trung gian \(k\), mảng \(dist\) chứa đường đi ngắn nhất giữa mọi cặp đỉnh mà chỉ đi qua các đỉnh trung gian thuộc tập \(\{1, 2, \ldots, k\}\).

graph LR
    subgraph "Floyd-Warshall: Thử đỉnh trung gian k"
        A["Khởi tạo dist[i][j]"] --> B["k = 1"]
        B --> C["Duyệt mọi cặp (i, j)"]
        C --> D{"dist[i][k] + dist[k][j] < dist[i][j]?"}
        D -->|"Có"| E["dist[i][j] = dist[i][k] + dist[k][j]"]
        D -->|"Không"| F["Giữ nguyên"]
        E --> G{"Hết cặp (i,j)?"}
        F --> G
        G -->|"Chưa"| C
        G -->|"Rồi"| H{"k < n?"}
        H -->|"Có"| I["k++"] --> C
        H -->|"Hết"| J["Hoàn thành"]
    end
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void floydWarshall(int n, vector<vector<long long>>& dist) {
    for (int k = 1; k <= n; k++) {          // duyệt đỉnh trung gian k
        for (int i = 1; i <= n; i++) {      // duyệt đỉnh nguồn i
            for (int j = 1; j <= n; j++) {  // duyệt đỉnh đích j
                if (dist[i][k] != LLONG_MAX && dist[k][j] != LLONG_MAX)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);  // cập nhật đường đi ngắn hơn
            }
        }
    }
}

1
2
3
4
5
6
def floyd_warshall(n, dist):
    for k in range(1, n + 1):          # duyệt đỉnh trung gian k
        for i in range(1, n + 1):      # duyệt đỉnh nguồn i
            for j in range(1, n + 1):  # duyệt đỉnh đích j
                if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])  # cập nhật đường đi ngắn hơn

Phân tích tính đúng đắn

Giải thích thứ tự vòng lặp — \(k\) PHẢI ở ngoài cùng:

Vòng lặp \(k\) là đỉnh trung gian. Khi xét \(k\), giả thiết là ta đã biết đường đi ngắn nhất giữa mọi cặp đỉnh chỉ dùng đỉnh trung gian \(\{1, \ldots, k-1\}\). Câu hỏi: đi qua đỉnh \(k\) có tốt hơn không?

Nếu \(k\) nằm trong cùng, ta sẽ cập nhật \(dist[i][j]\) bằng \(dist[i][k]\) và \(dist[k][j]\) mà có thể chưa được cập nhật với đầy đủ đỉnh trung gian → sai hoàn toàn.

Khởi tạo:

  • \(dist[i][i] = 0\) cho mọi \(i\).
  • \(dist[i][j] = w(i, j)\) nếu có cạnh \((i, j)\).
  • \(dist[i][j] = \infty\) nếu không có cạnh trực tiếp.

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

Sau khi chạy Floyd-Warshall, nếu \(dist[i][i] < 0\) thì đỉnh \(i\) nằm trong một chu trình âm.

Truy vết đường đi:

Dùng mảng \(next[i][j]\) để lưu đỉnh kề tiếp theo trên đường đi ngắn nhất từ \(i\) đến \(j\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int next[MAXN][MAXN];

void floydWithPath(int n, vector<vector<long long>>& dist) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            next[i][j] = (i != j && dist[i][j] < LLONG_MAX) ? j : -1;  // khởi tạo mảng next

    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] != LLONG_MAX && dist[k][j] != LLONG_MAX &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];  // cập nhật đường đi ngắn hơn
                    next[i][j] = next[i][k];  // cập nhật đỉnh kế tiếp trên đường đi
                }
            }
        }
    }
}

vector<int> getPath(int u, int v) {
    if (next[u][v] == -1) return {};  // không có đường đi
    vector<int> path = {u};
    while (u != v) {
        u = next[u][v];  // nhảy đến đỉnh kế tiếp
        path.push_back(u);
    }
    return path;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def floyd_with_path(n, dist):
    nxt = [[-1] * (n + 1) for _ in range(n + 1)]  # khởi tạo mảng next
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i != j and dist[i][j] < float('inf'):
                nxt[i][j] = j  # đỉnh kế tiếp trên đường đi

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]  # cập nhật đường đi ngắn hơn
                    nxt[i][j] = nxt[i][k]  # cập nhật đỉnh kế tiếp
    return nxt

def get_path(u, v, nxt):
    if nxt[u][v] == -1:
        return []  # không có đường đi
    path = [u]
    while u != v:
        u = nxt[u][v]  # nhảy đến đỉnh kế tiếp
        path.append(u)
    return path

Đánh giá độ phức tạp

Yếu tố Độ phức tạp
Thời gian \(O(n^3)\) — 3 vòng lặp lồng nhau, mỗi vòng \(n\) lần
Không gian \(O(n^2)\) — ma trận \(dist\) kích thước \(n \times n\)

Lưu ý thực tế: Floyd-Warshall hiệu quả khi \(n \leq 500\). Với \(n > 500\), \(O(n^3)\) quá chậm, cân nhắc chạy Dijkstra/Bellman-Ford từ mỗi đỉnh.

3. Ứng dụng

3.1. Bao đóng bắc giác (Transitive Closure)

Dùng Floyd-Warshall với toán tử \(\lor\) thay vì \(\min\), \(\land\) thay vì \(+\):

1
2
3
4
5
6
7
bool reach[MAXN][MAXN];

void transitiveClosure(int n) {
    for (int k = 1; k <= n; k++)          // duyệt đỉnh trung gian k
        for (int i = 1; i <= n; i++)      // duyệt đỉnh nguồn i
            for (int j = 1; j <= n; j++)  // duyệt đỉnh đích j
                reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);  // OR logic thay vì min

1
2
3
4
5
def transitive_closure(n, reach):
    for k in range(1, n + 1):          # duyệt đỉnh trung gian k
        for i in range(1, n + 1):      # duyệt đỉnh nguồn i
            for j in range(1, n + 1):  # duyệt đỉnh đích j
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])  # OR logic

3.2. Tìm chu trình âm và in ra

Dùng Bellman-Ford kết hợp mảng \(parent\) để truy vết chu trình:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
bool bellmanFordWithPath(int n, int s, vector<tuple<int,int,int>>& edges,
                         vector<long long>& dist, vector<int>& parent) {
    dist.assign(n + 1, LLONG_MAX);  // khởi tạo khoảng cách
    parent.assign(n + 1, -1);        // khởi tạo mảng cha
    dist[s] = 0;

    int lastUpdated = -1;
    for (int i = 1; i < n; i++) {       // lặp n-1 lần
        for (auto [u, v, w] : edges) {   // duyệt từng cạnh
            if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;   // thư giãn cạnh (u,v)
                parent[v] = u;           // lưu cha cho truy vết
            }
        }
    }

    for (auto [u, v, w] : edges) {       // kiểm tra chu trình âm
        if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
            parent[v] = u;
            lastUpdated = v;             // đánh dấu đỉnh trong chu trình âm
            break;
        }
    }

    if (lastUpdated == -1) return false; // không có chu trình âm

    vector<int> cycle;
    int x = lastUpdated;
    for (int i = 0; i < n; i++) x = parent[x];  // tìm đỉnh trong chu trình
    int cur = x;
    do {
        cycle.push_back(cur);
        cur = parent[cur];
    } while (cur != x);
    cycle.push_back(x);
    reverse(cycle.begin(), cycle.end());  // đảo ngược để có thứ tự xuôi

    cout << "Chu trinh am: ";
    for (int v : cycle) cout << v << " ";
    return true;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def bellman_ford_with_path(n, s, edges):
    dist = [float('inf')] * (n + 1)  # khởi tạo khoảng cách
    parent = [-1] * (n + 1)          # khởi tạo mảng cha
    dist[s] = 0

    last_updated = -1
    for _ in range(n - 1):            # lặp n-1 lần
        for u, v, w in edges:          # duyệt từng cạnh
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w  # thư giãn cạnh (u,v)
                parent[v] = u          # lưu cha cho truy vết

    for u, v, w in edges:              # kiểm tra chu trình âm
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            parent[v] = u
            last_updated = v           # đánh dấu đỉnh trong chu trình âm
            break

    if last_updated == -1:
        return False, [], dist         # không có chu trình âm

    x = last_updated
    for _ in range(n):
        x = parent[x]                  # tìm đỉnh trong chu trình
    cycle = []
    cur = x
    while True:
        cycle.append(cur)
        cur = parent[cur]
        if cur == x:
            cycle.append(cur)
            break
    cycle.reverse()                    # đảo ngược để có thứ tự xuôi
    return True, cycle, dist

3.3. Thuật toán Johnson — APSP cho đồ thị thưa

Khi đồ thị thưa (\(m \ll n^2\)), Floyd-Warshall \(O(n^3)\) lãng phí. Johnson kết hợp Bellman-Ford + Dijkstra:

  1. Thêm đỉnh ảo \(0\), nối đến mọi đỉnh với trọng số \(0\).
  2. Chạy Bellman-Ford từ đỉnh \(0\) → lấy potential \(h[v]\).
  3. Cập nhật trọng số: \(w'(u,v) = w(u,v) + h[u] - h[v]\) → mọi trọng số \(\geq 0\).
  4. Chạy Dijkstra từ mỗi đỉnh trên đồ thị trọng số mới.
  5. Khôi phục khoảng cách thực: \(dist(u,v) = dist'(u,v) - h[u] + h[v]\).

Độ phức tạp: \(O(nm + n \cdot m \log n)\), tốt hơn \(O(n^3)\) khi đồ thị thưa.

4. So sánh các thuật toán đường đi ngắn nhất

Thuật toán Loại Trọng số âm? Chu trình âm? Độ phức tạp
BFS 1 nguồn, không trọng số Không Không \(O(n + m)\)
Dijkstra 1 nguồn Không Không \(O(m \log n)\)
Bellman-Ford 1 nguồn Có Phát hiện \(O(nm)\)
Floyd-Warshall Mọi cặp Có Phát hiện \(O(n^3)\)

Chọn thuật toán phù hợp:

Tình huống Thuật toán
Đồ thị không trọng số BFS
Trọng số \(\geq 0\), 1 nguồn Dijkstra
Có trọng số âm Bellman-Ford
Cần đường đi ngắn nhất mọi cặp, \(n \leq 500\) Floyd-Warshall
Cần phát hiện chu trình âm Bellman-Ford hoặc Floyd-Warshall

5. Lưu ý quan trọng

  • Dijkstra SAI khi có trọng số âm → bắt buộc dùng Bellman-Ford.
  • Floyd-Warshall: Khởi tạo \(dist[i][i] = 0\), \(dist[i][j] = \infty\) nếu không có cạnh trực tiếp.
  • Tràn số: Dùng long long trong C++, kiểm tra != LLONG_MAX trước khi cộng để tránh tràn.
  • Thứ tự vòng lặp Floyd: \(k\) PHẢI ở ngoài cùng. Đặt \(k\) trong cùng sẽ cho kết quả sai hoàn toàn.
  • Đồ thị vô hướng + cạnh âm: Mỗi cạnh vô hướng coi như 2 cạnh có hướng.
  • Floyd-Warshall phát hiện chu trình âm: Nếu \(dist[i][i] < 0\) sau khi chạy, đỉnh \(i\) nằm trong chu trình âm.
  • Bellman-Ford chỉ phát hiện chu trình âm reachable từ đỉnh nguồn. Để phát hiện mọi chu trình âm, thêm đỉnh ảo hoặc chạy từ mỗi thành phần liên thông.

6. Bài tập luyện tập

Bài Nền tảng Độ khó Chủ đề
CSES - Shortest Routes II CSES ⭐⭐ Floyd-Warshall
CSES - Cycle Finding CSES ⭐⭐⭐ Bellman-Ford + chu trình âm
CSES - Flight Discount CSES ⭐⭐⭐ Dijkstra nâng cao
SPOJ - NEGGRAPH SPOJ ⭐⭐⭐ Bellman-Ford
VNOJ - NKPATH VNOJ ⭐⭐⭐ Floyd + DP
VNOJ - QBMST VNOJ ⭐⭐ MST cơ bản
VNOJ - DIJKSTRA VNOJ ⭐⭐ Dijkstra trực tiếp
LeetCode - Network Delay Time LeetCode ⭐⭐ Dijkstra/Floyd
LeetCode - Cheapest Flights Within K Stops LeetCode ⭐⭐⭐ Bellman-Ford variant
LeetCode - Find the City LeetCode ⭐⭐ Floyd-Warshall

Bài tập thực hành trên FPTOJ

Dưới đây là danh sách 25 bài tập thực hành được đồng bộ trên hệ thống FPTOJ:

Mã bài Tên bài tập Độ khó Chuyên đề Bản chất bài tập Lời giải chi tiết
bf-shortest Hành trình xuyên thung lũng ⭐⭐ Bellman-Ford Đường ngắn nhất có cạnh âm Xem hướng dẫn
bf-negative Đầu tư năng lượng ⭐⭐ Bellman-Ford Di chuyển trạm sạc pin Xem hướng dẫn
bf-cycle Vòng lặp thời gian ⭐⭐⭐ Bellman-Ford Phát hiện chu trình âm từ ~S~ Xem hướng dẫn
bf-path Đồng bộ năng lượng hệ thống ⭐⭐⭐ Bellman-Ford Khoảng cách ngắn nhất từ nguồn Xem hướng dẫn
bf-arbitrage Tỷ giá chênh lệch ⭐⭐⭐ Bellman-Ford Arbitrage qua log tỷ giá Xem hướng dẫn
bf-transit Giới hạn số chặng bay ⭐⭐⭐ Bellman-Ford Đường ngắn nhất đi tối đa ~K~ cạnh Xem hướng dẫn
bf-safety Hệ số an toàn ⭐⭐⭐ Bellman-Ford Dijkstra trên log xác suất Xem hướng dẫn
bf-limit Hành trình có điều kiện ⭐⭐⭐ Bellman-Ford Trạng thái giới hạn cạnh hiểm trở ~C~ Xem hướng dẫn
bf-longest Hành trình cổ vật ⭐⭐⭐ Bellman-Ford Đường đi dài nhất trên DAG Xem hướng dẫn
bf-maxstep Địa chấn lòng đất ⭐⭐⭐ Bellman-Ford Khoảng cách ngắn nhất đúng ~K~ bước Xem hướng dẫn
bf-toll Hành trình tối ưu ⭐⭐⭐ Bellman-Ford Đường ngắn nhất và truy vết tối ưu kép Xem hướng dẫn
bf-teleport Nghịch lý thời gian ⭐⭐⭐⭐ Bellman-Ford Chu trình âm ảnh hưởng tới đích Xem hướng dẫn
bf-island Neo đậu tránh bão ⭐⭐⭐⭐ Bellman-Ford Tìm và truy vết cụ thể chu trình âm Xem hướng dẫn
fw-basic Liên lạc nội bộ ⭐⭐ Floyd-Warshall Floyd-Warshall cơ bản giữa mọi cặp Xem hướng dẫn
fw-reachable Mạng lưới giao thông ⭐⭐ Floyd-Warshall Bao đóng chuyển tiếp tính liên thông Xem hướng dẫn
fw-maxweight Mạng lưới tải trọng ⭐⭐ Floyd-Warshall Bottleneck path tối đa cầu yếu nhất Xem hướng dẫn
fw-dynamic Cầu nối giao thông mới ⭐⭐ Floyd-Warshall Cập nhật ma trận Floyd khi thêm cạnh Xem hướng dẫn
fw-diameter Đường kính mạng lưới ⭐⭐⭐ Floyd-Warshall Độ trễ ngắn nhất lớn nhất Xem hướng dẫn
fw-central Trạm cứu hỏa trung tâm ⭐⭐⭐ Floyd-Warshall Tâm của đồ thị tối thiểu max khoảng cách Xem hướng dẫn
fw-bypass Đóng cửa sửa đường ⭐⭐⭐ Floyd-Warshall Tìm chu trình có độ dài nhỏ nhất Xem hướng dẫn
fw-hubs Các trung tâm trung chuyển ⭐⭐⭐ Floyd-Warshall Đường ngắn nhất đi qua ít nhất một hub Xem hướng dẫn
fw-minimax Hành trình êm ái ⭐⭐⭐ Floyd-Warshall Minimax path tối thiểu cạnh lớn nhất Xem hướng dẫn
fw-transit Xây dựng trạm trung chuyển ⭐⭐⭐ Floyd-Warshall Chọn đỉnh ~X~ tối ưu tổng khoảng cách Xem hướng dẫn
fw-multicycle Lan truyền chu trình âm ⭐⭐⭐ Floyd-Warshall Floyd-Warshall lan truyền chu trình âm Xem hướng dẫn
fw-density Mạng lưới dày đặc ⭐⭐⭐⭐ Floyd-Warshall Thêm đỉnh ngược thời gian Xem hướng dẫn

Bài viết liên quan

Tài liệu tham khảo

💬 Bình luận