Chương trình C++ tìm số lượng đường đi rời rạc cạnh tối đa

Tìm số lượng đường đi rời rạc cạnh (edge-disjoint paths) tối đa giữa hai đỉnh, tương đương luồng cực đại.

Thuật toán

Bắt đầu
  hàm bfs() trả về true nếu có đường từ s đến t trong đồ thị dư.
  hàm findDisPath() trả về luồng cực đại:
    A) Khởi tạo flow = 0.
    B) Nếu có đường tăng luồng, thêm vào flow.
    C) Trả về flow.
Kết thúc

Ví dụ

#include <iostream>
#include <climits>
#include <cstring>
#include <queue>
#define n 7
using namespace std;

bool bfs(int g[n][n], int s, int t, int par[]) {
    bool visit[n];
    memset(visit, 0, sizeof(visit));
    queue<int> q;
    q.push(s);
    visit[s] = true;
    par[s] = -1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v = 0; v < n; v++) {
            if (!visit[v] && g[u][v] > 0) {
                q.push(v);
                par[v] = u;
                visit[v] = true;
            }
        }
    }
    return (visit[t] == true);
}

int findDisPath(int G[n][n], int s, int t) {
    int u, v;
    int g[n][n];
    for (u = 0; u < n; u++)
        for (v = 0; v < n; v++)
            g[u][v] = G[u][v];
    int par[n];
    int max_flow = 0;
    while (bfs(g, s, t, par)) {
        int path_flow = INT_MAX;
        for (v = t; v != s; v = par[v]) {
            u = par[v];
            path_flow = min(path_flow, g[u][v]);
        }
        for (v = t; v != s; v = par[v]) {
            u = par[v];
            g[u][v] -= path_flow;
            g[v][u] += path_flow;
        }
        max_flow += path_flow;
    }
    return max_flow;
}

int main() {
    int g[n][n] = {{0, 6, 7, 1},
                   {0, 0, 4, 2},
                   {0, 5, 0, 0},
                   {0, 0, 19, 12},
                   {0, 0, 0, 17},
                   {0, 0, 0, 0}};
    int s = 0, d = 3;
    cout << " There exist maximum " << findDisPath(g, s, d) << " edge-disjoint paths from " << s << " to " << d;
    return 0;
}

Kết quả

There exist maximum 3 edge-disjoint paths from 0 to 3