Edmonds Karp Max Flow 알고리즘의 일부 경로가 누락되었습니다
-
12-11-2019 - |
문제
Edmond Karp 알고리즘 이지만, 올바르지 않아요. 올바른 흐름을 얻지 못하고 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을 더 잘 흐르게 할 수 있습니다. Wiki 샘플 코드에서 알고리즘을 구현했습니다. 나는 우리가 유효한 경로를 사용할 수 없다고 생각하고 실제로이 탐욕스러운 선택이 잘못되었습니다.
나는 틀렸어?
코드는 아래에 있습니다 (C #에서는 임계 값이 0이며 알고리즘에 영향을주지 않습니다) :
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;
}
. 해결책
경로를 선택하는 방법은 중요하지 않습니다.
경로 용량이있는 역순으로 경로의 가장자리를 추가하고 해당 값으로 경로의 가장자리 용량을 줄여야합니다.
사실이 솔루션은 작동합니다 :
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.
}
.
마지막으로 최대 유량 값은 루프의 C
의 합계입니다.
최대 흐름에서 가장자리의 흐름을 보려면, 초기 그래프를 어딘가에 유지할 수 있습니다. 가장자리 E의 흐름은 Original_capacity_e - current_capacity_e입니다.