Missing some paths in karp max edmonds stream algorithm

Question

I would apply the Edmond Karp algorithm , but it seems that this is not correct, and I am not getting the correct flow, consider the following graph and flow from 4 to 8:

The algorithm is performed as follows:

First it finds 4 → 1 → 8, Then it finds 4 → 5 → 8 after that 4 → 1 → 6 → 8

And I think the third way is wrong, because using this path, we cannot use the stream from 6 → 8 (because it was used), and in fact we cannot use the stream from 4 → 5 → 6 → 8.

Indeed, if we choose 4 → 5 → 6 → 8, and then 4 → 1 → 3 → 7 → 8, and then 4 → 1 → 3 → 7 → 8, we get the best flow (40).

I implemented the algorithm from the wiki sample code. I think that we cannot use any right way, and in fact this greedy choice is wrong.

I am wrong?

The code is as follows (in C #, the threshold is 0 and does not 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; } 

Answer 1

The way you choose the paths is not important.

You must add the edges of the path in the reverse order with bandwidth and reduce the capacity of the edges of the path by this value.

Actually 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 maximum flow value is the sum of C in the loop.

If you want to see the stream in edges in the maximum stream you made, you can save the initial graph somewhere, the stream in edge e will be original_capacity_e - current_capacity_e.