The ford fulkerson complexity is O(FE), but the edmond karps is O(VE^2). This is based on the premise that every edge can only be critical O(V) number of times, and this applies to all the edge so we have O(VE) number of times possible that an edge can go critical, i.e. the number of times the augmenting path can be found. This makes sense since we can spend O(V) number of times utilizing just 1 edge, and then since we need to do so for every other edge in the graph, we get O(VE) times we need to find the augmenting path. Then the BFS takes O(E), so we get our final complexity of edmonds karp as required.
But the problem is this: the O(VE) argument for number of augmenting paths is so general, so why can't this analysis be applied to ford fulkerson? It seems that the complexities of the two algorithms are compared on an unfair basis. What is it in the edmonds karp algorithm that makes it superior?
Also, why is it that when we use the BFS approach in edmonds karp, we are guaranteed to find the shortest path? Is there a short proof to this?
