缺少埃德蒙兹卡普最大流算法一些路径 [英] Missing some paths in edmonds karp max flow algorithm
问题描述
我想实现埃德蒙·卡普算法，但似乎这不是正确的，我没有得到正确的流量，可以考虑下面的图像，并从4流向8：
算法运行：
首先找到4→1→8， 然后发现4→5→8 后4→1→6→8
我认为第三条道路是错误的，因为通过这条道路，我们不能从6→8使用流量（因为它使用），而事实上，我们不能用流量从4→5→6→8。
在如果我们选择4→5→6→8，然后4→1→3→7→8和事实然后4→1→3→7→8我们可以获得更好的流动（40）。
我实现了从维基样品code算法。我认为，我们不能使用任何有效的路径，实际上这个贪婪的选择是错误的。
难道我错了吗？
code是如以下（在c＃，阈值为0，并且不影响该算法）：
公共小数EdmondKarps（十进制[] []容量/ *容量矩阵* /，
名单＆LT; INT＆GT; []邻居/ *邻居列表* /，
的int / *源* /，
INT T / *片* /，
十进制门槛，
出小数[] [] flowMatrix
/ * flowMatrix（矩阵给出的最大值合法flowMatrix）* /
）
{
阈值=阈值;
INT N = capacities.Length;
十进制流量=0米; //（初始flowMatrix为零）
flowMatrix =新小数[N] []; //array(1..n，1..N）（从u剩余容量v是能力[U，V] - flowMatrix [U，V]）
的for（int i = 0;我n种;我++）
{
flowMatrix [我] =新小数[N];
}
而（真）
{
VAR路径=新的INT [N];
VAR pathCapacity = BreadthFirstSearch（能力，邻居，S，T，flowMatrix，出路径）;
如果（pathCapacity＆LT; =阈值）
打破;
流量+ = pathCapacity;
//（原路返回搜索和更新flowMatrix）
变种V =吨;
而（ⅴ！= S）
{
变种U =路径[V]
flowMatrix [U] [V] = flowMatrix [U] [V] + pathCapacity;
flowMatrix [V] [U] = flowMatrix [V] [U] - pathCapacity;
V = U;
}
}
回流;
}
私人小数BreadthFirstSearch（十进制[] []的能力，列表和LT; INT＆GT; []邻居，int类型，INT T，小数[] [] flowMatrix，OUT INT []路径）
{
变种N = capacities.Length;
路径= Enumerable.Range（0，n）的。选择（X =＆-1）〜.ToArray（）; //阵列（1..N）
路径[S] = -2;
VAR pathFlow =新小数[N];
pathFlow [S] = Decimal.MaxValue; // INFINT
变种Q =新的队列和LT;诠释＆GT;（）; // Q是完全队列:)
Q.Enqueue（多个）;
而（Q.Count大于0）
{
变种U = Q.Dequeue（）;
的for（int i = 0; I＆LT;邻居[U] .Count之间;我++）
{
变种V =邻居[U] [我]
//（如果有可用的容量，和v不之前见于搜索）
如果（容量[U] [V] - flowMatrix [U] [V]≥阈值安培;＆安培;路径[V] == -1）
{
//保存路径：
路径[V] = U;
pathFlow [V] = Math.Min（pathFlow [U]，容量[U] [V] - flowMatrix [U] [V]）;
如果（V！= T）
Q.Enqueue（五）;
其他
返回pathFlow [T]
}
}
}
返回0;
}
选择路径的方式并不重要。
您有由该值来添加顺序相反的路径的边缘与路径容量和减少的路径的边的能力
其实这个解决方案的工作原理：
同时存在与源正容量下沉{路径
找到从源头正面能力击沉任何路径，命名为P容量C.
加入C到maximum_flow_value。
降低C来自P的边缘的能力
加入C到reverse_P边缘的能力。
}
最后，最大流量值是在循环的S ç总和。
如果你想看到的最大流量所做的流动在边缘，你可以保留初始图的某个地方，在边e流将original_capacity_e - current_capacity_e
I'd implement Edmond Karp algorithm, but seems it's not correct and I'm not getting correct flow, consider following graph and flow from 4 to 8:
Algorithm runs as follow:
First finds 4→1→8, Then finds 4→5→8 after that 4→1→6→8
And I think third path is wrong, because by using this path we can't use flow from 6→8 (because it used), and in fact we can't use flow from 4→5→6→8.
In fact if we choose 4→5→6→8, and then 4→1→3→7→8 and then 4→1→3→7→8 we can gain better flow(40).
I Implemented algorithm from wiki sample code. I think we can't use any valid path and in fact this greedy selection is wrong.
Am I wrong?
Code is as below (in c#, threshold is 0, and doesn't affect the algorithm):
public decimal EdmondKarps(decimal[][] capacities/*Capacity matrix*/,
List<int>[] neighbors/*Neighbour lists*/,
int s /*source*/,
int t/*sink*/,
decimal threshold,
out decimal[][] flowMatrix
/*flowMatrix (A matrix giving a legal flowMatrix with the maximum value)*/
)
{
THRESHOLD = threshold;
int n = capacities.Length;
decimal flow = 0m; // (Initial flowMatrix is zero)
flowMatrix = new decimal[n][]; //array(1..n, 1..n) (Residual capacity from u to v is capacities[u,v] - flowMatrix[u,v])
for (int i = 0; i < n; i++)
{
flowMatrix[i] = new decimal[n];
}
while (true)
{
var path = new int[n];
var pathCapacity = BreadthFirstSearch(capacities, neighbors, s, t, flowMatrix, out path);
if (pathCapacity <= threshold)
break;
flow += pathCapacity;
//(Backtrack search, and update flowMatrix)
var v = t;
while (v != s)
{
var u = path[v];
flowMatrix[u][v] = flowMatrix[u][v] + pathCapacity;
flowMatrix[v][u] = flowMatrix[v][u] - pathCapacity;
v = u;
}
}
return flow;
}
private decimal BreadthFirstSearch(decimal[][] capacities, List<int>[] neighbors, int s, int t, decimal[][] flowMatrix, out int[] path)
{
var n = capacities.Length;
path = Enumerable.Range(0, n).Select(x => -1).ToArray();//array(1..n)
path[s] = -2;
var pathFlow = new decimal[n];
pathFlow[s] = Decimal.MaxValue; // INFINT
var Q = new Queue<int>(); // Q is exactly Queue :)
Q.Enqueue(s);
while (Q.Count > 0)
{
var u = Q.Dequeue();
for (int i = 0; i < neighbors[u].Count; i++)
{
var v = neighbors[u][i];
//(If there is available capacity, and v is not seen before in search)
if (capacities[u][v] - flowMatrix[u][v] > THRESHOLD && path[v] == -1)
{
// save path:
path[v] = u;
pathFlow[v] = Math.Min(pathFlow[u], capacities[u][v] - flowMatrix[u][v]);
if (v != t)
Q.Enqueue(v);
else
return pathFlow[t];
}
}
}
return 0;
}
The way to choose paths is not important.
You have to add edges of the path in reverse order with path capacity and reduce capacity of edges of the path by that value.
In fact this solution works:
while there is a path with positive capacity from source to sink{
find any path with positive capacity from source to sink, named P with capacity C.
add C to maximum_flow_value.
reduce C from capacity of edges of P.
add C to capacity of edges of reverse_P.
}
Finally the value of maximum-flow is sum of Cs in the loop.
If you want to see the flow in edges in the maximum-flow you made, you can retain the initial graph somewhere, the flow in edge e would be original_capacity_e - current_capacity_e.
这篇关于缺少埃德蒙兹卡普最大流算法一些路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
