โปรแกรม C++ หาจำนวน Edge-Disjoint Paths สูงสุด

บทนำ

นี่คือโปรแกรม C++ หาจำนวน Edge-Disjoint Paths สูงสุด ซึ่งหมายถึง shortest subset path หรือ maximum flow ระหว่างสองโหนด

อัลกอริทึม

Begin
  function bfs() คืนค่า true ถ้ามี path จาก source s ถึง sink t ใน residual graph
End

Begin
  function findDisPath() คืนค่า maximum flow ในกราฟที่กำหนด:
    A) เริ่มต้น flow = 0
    B) ถ้ามี augmenting path จาก source ถึง sink ให้เพิ่ม path นั้นเข้า flow
    C) คืนค่า flow
End

ตัวอย่างโค้ด

#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] == false && 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;
}

ผลลัพธ์

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