How to start Edmonds-Karp implementation if all the paths have same lengths?

Question

How can I select the starting path for the Edmonds-Karp algorithm if all the paths are the same length? In this case, maximum flow changes according to path sequence decision.

Answer 1

I think there is a problem with how you handle capacities at the vertices. The usual way this is done is by splitting the vertex v in two vertices v' and v'' and adding an edge between v' and v'' with the capacity of the vertex. All edges connected to v(i.e. for which v is destination) should be connected with v' in the new graph and all edges from v should start from v'' in the new graph.

You probably know that when you let flow x-a-b-y 3 you add to the capacity of the reverse edges. In that case you will add the edges a x 3, b a 3, y b 3. If you do the graph representation as I described you will see that there is additional flow you can use in the first case(I think it can pass through x-a-d-c-b-y, but have not checked it).

The selection of the shortest path should not change the answer - as I mentioned in my comment we only select the shortest path on each step to avoid bad cases where the performance suffers, but the answer is always the same.

Hope this answer helps.