Search code examples
algorithmedmonds-karp

How do we break a tie in shortest length of augmenting in the edmonds-karp algorithm?

So if the 2 shortest augmenting paths are length 2, what is the secondary filter?

From what I understand, Edmonds-Karp chooses the shortest path, that is, the path with the least amount of edges.

However, both of these paths are length 2. So does this algorithm then extend and say "choose the path with max/min flow" ?

enter image description here

Solution

  • It doesn't matter which path is chosen. The proof of correctness and complexity still go through.