福特富尔克森算法

2023-06-21 05:58:02 311

Ford-Fulkerson算法用于检测给定图中从起始顶点到汇顶点的最大流量。在这个图中，每条边都有容量。提供了两个名为Source和Sink的顶点。源顶点全是外边，没有内边，而汇点全是内边，没有外边。

有一些限制：

边上的流量不超过该图的给定容量。

除了源和汇之外，每条边的流入和流出也是相等的。

输入和输出

Input:
The adjacency matrix:
0 10 0 10 0  0
0  0 4  2 8  0
0  0 0  0 0 10
0  0 0  0 9  0
0  0 6  0 0 10
0  0 0  0 0  0

Output:
最大流量为： 19

算法

bfs(vert,start,sink)

输入： 顶点列表、起始节点和汇节点。

输出- 访问接收器时为真。

Begin
   initially mark all nodes as unvisited
   state of start as visited
   predecessor of start node is φ
   insert start into the queue qu
   while qu is not empty, do
      delete element from queue and set to vertex u
      for all vertices i, in the residual graph, do
         if u and i are connected, and i is unvisited, then
            add vertex i into the queue
            predecessor of i is u
            mark i as visited
      done
   done
   return true if state of sink vertex is visited
End

fordFulkerson(vert,source,sink)

输入：顶点列表、源顶点和汇顶点。

输出- 从开始到下沉的最大流量。

Begin
   create a residual graph and copy given graph into it
   while bfs(vert, source, sink) is true, do
      pathFlow := ∞
      v := sink vertex
      while v ≠ start vertex, do
         u := predecessor of v
         pathFlow := minimum of pathFlow and residualGraph[u, v]
         v := predecessor of v
      done

      v := sink vertex
      while v ≠ start vertex, do
         u := predecessor of v
         residualGraph[u,v] := residualGraph[u,v] – pathFlow
         residualGraph[v,u] := residualGraph[v,u] – pathFlow
         v := predecessor of v
      done

      maFlow := maxFlow + pathFlow
   done
   return maxFlow
End

示例

#include
#include
#define NODE 6
using namespace std;

typedef struct node {
   int val;
   int state; //status
   int pred; //predecessor
}node;

int minimum(int a, int b) {
   return (a que;

   for(i = 0; i 0 && vert[i].state == 0) {
            que.push(vert[i]);
            vert[i].pred = u.val;
            vert[i].state = 1;
         }
      }
   }
   return (vert[sink.val].state == 1);
}

int fordFulkerson(node *vert, node source, node sink) {
   int maxFlow = 0;
   int u, v;

   for(int i = 0; i输出结果最大流量为： 19

福特富尔克森算法

输入和输出

算法

示例

热门推荐

随机推荐