Edmonds -Karp 算法是Ford-Fulkerson 方法的变体。它用于确定流量网络中的最大流量。它通过采用BFS（广度优先搜索）来定位具有最少边数的增广路径，从而提高了Ford-Fulkerson 算法的有效性。通过这样做，保证算法以O(VE2) 时间复杂度运行，其中V是图顶点的数量，E是图边的数量。
流量网络：
流网络由有向图组成，其中每条边都分配有容量（它可以支持的最大流量）和流量（通过它的流量）。目标是在考虑边的容量限制的同时确定源顶点和汇顶点之间的最大流量。
算法步骤：
Edmonds-Karp算法有以下步骤：
1、初始化：
将剩余容量矩阵的初始值设置为与容量矩阵相同的值。图邻接表初始化。
2. 增加路径：
找到一条使用BFS增强的从源头到洗脸盆的路径。当从源点到汇点的道路包含可用容量大于 0 的边时，该路径被称为增广路径。
BFS保证我们发现具有最少边缘的增广路径，这是 Edmonds-Karp 算法的一个重要方面。
3.流程更新：
发现增广路径后，确定可沿路径发送的最高流量。增广路径中的所有边都具有这样的最小容量。
通过从前向边缘减去流量并将其添加到后向边缘，可以更新沿着增强路径的剩余能力的前向和后向边缘。
4. 重复：
当无法找到更多增强途径时，再次重复步骤 2和3 。
5. 终止：
当没有检测到额外的增强途径时，该过程结束。离开源头的所有流量的总和是可以获得的最大流量。
C++中的实现信息：
Edmonds -Karp 算法是使用提供的 C++ 代码通过以下方式实现的：
- 它采用称为邻接表的图形表示形式，其中adj保存有关顶点 u 的信息
- 存储边容量的容量矩阵的初始值为0。
- BFS由bfs 函数执行，然后返回可以沿路径传递的最大流量来定位增广路径。
- 用户在主函数中输入节点数、边数、边容量、源和汇。
- 由于算法使用bfs 函数来定位增强路径，因此网络流量得到更新。
- 计算并写在结论处就是最大流量。
Edmonds-Karp 算法的操作概述：- 将每条边的流量初始化为0。
- 当存在增广路径（从水源到洗脸盆且所有边缘均具有可用容量的路径）时，请执行以下操作：[list=1]
- 要确定增广路径，请执行从源头到洗脸盆的 BFS。仅考虑 BFS 期间具有可用容量的边。
- 如果找不到增广路径，则停止算法，因为不可能再有进一步的进展。
- 确定沿已发现的增广路径的路径的最小容量（剩余容量） 。这将是网络可以容纳的最大流量。
- 通过移除后向边缘（以表示反向流）并添加到前向边缘（以更新沿增强通道的流），最小容量被应用于前向边缘。
将离开源顶点的流量相加以确定总体流量。
我们用一个程序来说明C++中的Edmonds-Karp算法：
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
int capacities[10][10];
int flowPassed[10][10];
vector<int>graph[10];
int parentsList[10];
int currentPathCapacity[10];
int bfs(int startNode, int endNode)
{
memset(parentsList, -1, sizeof(parentsList));
memset(currentPathCapacity, 0, sizeof(currentPathCapacity));
queue<int> q;
q.push(startNode);
parentsList[startNode] = -2;
currentPathCapacity[startNode] = 999;
while(!q.empty())
{
int currentNode = q.front();
q.pop();
for(int i=0; i<graph[currentNode].size(); i++)
{
int to = graph[currentNode]<i>;
if(parentsList[to] == -1)
{
if(capacities[currentNode][to] - flowPassed[currentNode][to] > 0)
{
parentsList[to] = currentNode;
currentPathCapacity[to] = min(currentPathCapacity[currentNode],
capacities[currentNode][to] - flowPassed[currentNode][to]);
if(to == endNode)
{
return currentPathCapacity[endNode];
}
q.push(to);
}
}
}
}
return 0;
}
int edmondsKarp(int startNode, int endNode)
{
int maxFlow = 0;
while(true)
{
int flow = bfs(startNode, endNode);
if (flow == 0)
{
break;
}
maxFlow += flow;
int currentNode = endNode;
while(currentNode != startNode)
{
int previousNode = parentsList[currentNode];
flowPassed[previousNode][currentNode] += flow;
flowPassed[currentNode][previousNode] -= flow;
currentNode = previousNode;
}
}
return maxFlow;
}
int main()
{
int nodesCount, edgesCount;
cout<<"enter the number of nodes and edges\n";
cin>>nodesCount>>edgesCount;
int source, sink;
cout<<"enter the source and sink\n";
cin>>source>>sink;
for(int edge = 0; edge <edgesCount; edge++)
{
cout<<"enter the start and end vertex along with capacity\n";
int from, to, capacity;
cin>>from>>to>>capacity;
capacities[from][to] = capacity;
graph[from].push_back(to);
graph[to].push_back(from);
}
int maxFlow = edmondsKarp(source, sink);
cout<<endl<<endl<<"Max Flow is:"<<maxFlow<<endl;
}
输出：
enter the number of nodes and edges
6
10
enter the source and sink
0
5
enter the start and end vertex along with the capacity
0
1
16
enter the start and end vertex along with the capacity
0
2
13
enter the start and end vertex along with capacity
1
2
10
enter the start and end vertex along with capacity
2
1
4
enter the start and end vertex along with capacity
1
3
12
enter the start and end vertex along with capacity
3
2
9
enter the start and end vertex along with capacity
2
4
14
enter the start and end vertex along with capacity
4
3
7
enter the start and end vertex along with capacity
4
5
4
enter the start and end vertex along with capacity
3
5
20
Max Flow is:23
|
代码以几条 #include 指令开始，这些指令添加了输入/输出操作、队列处理、文本操作和向量使用所需的头文件。
代码声明并初始化了不同的数组和向量，以存储有关流量网络的数据：
- 容量[10][10]：连接节点的边的容量存储在这个数组中。capacity[j]是一个二维数组，存储从节点 i 到节点 j 的容量。
- flowPassed[10][10]：此数组中存储了连接节点的每条边上的流量。
- vectorgraph[10]：图的邻接关系列表由该向量数组显示。与每个元素相连的向量记录了由边连接的节点，每个元素是一个节点。
- parentsList[10]：这是一个数组，记录了 BFS 遍历所遵循的路径。
- currentPathCapacity[10]：这是一个数组，用于记录当前正在检查的路径的能力。
bfs 函数旨在执行从起点节点到终点节点的 "广度优先搜索"（Breadth-First Search），以找到具有可用容量的增强路径。具有可处理更多流量的边的源到汇路径称为增强路径。
BFS 算法采用队列逐层探索节点。在遍历过程中会更新 currentPathCapacity，以跟踪路径和路径的最小容量。
核心埃德蒙兹-卡普算法是通过 edmondsKarp 函数实现的。在找不到增量路径之前，它会反复调用 bfs 函数来定位增量路径，并沿着这些路径调整流量。从源头到洗脸盆，它发送的是整个最大流量。
- 只要还有流量需要增加，该函数内部的 while 循环就会不断寻找增加流量的方法。
- 流量变量来自 bfs 函数，该函数决定了当前路径上可增加的最大流量。
- 图形中的流量改变后，循环会修改 flowPassed 数组。
主函数是执行的起点：
- 它接受节点、边、源和汇数量的输入。
- 它通过遍历每条边来填充容量数组和图的邻接列表，同时收集起点节点、终点节点和容量的输入。
- 最后，它使用 Edmonds Karp 函数确定最大流量并输出结果。
代码采用 Edmonds-Karp 方法来解决流量网络中的最大流量问题。BFS 用于定位增强路径，以计算从源到汇的最大流量。之后，它会更新流经网络的流量，直到找不到更多的增强路径为止。