查找最大边不相交路径数的 C++ 程序

• Z时代
• 2024-01-10
• 分类：综合

这是一个 C++ 程序，用于查找边不相交路径的最大数量，这意味着两个顶点之间的最短子集路径或最大流量。

算法：

Begin
   function bfs() returns true if there is path from source s to sink t in
   the residual graph which indicates additional possible flow in the
   graph.
End
Begin
   function findDisPath() is used to return maximum flow in given
   graph:
   A) Initiate flow as 0.
   B) If there is an augmenting path from source to sink, add the path to flow.
   C) Return 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)<< " 从边缘不相交的路径 " << s <<" to "<<d;
   return 0;
}

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

以上是 查找最大边不相交路径数的 C++ 程序 的全部内容， 来源链接： utcz.com/z/335617.html