Почему сложность алгоритма Эдмондса-Карпа меньше, чем у алгоритма Форда-Фулкерсона?
Форд Фулкерсон сложность O(FE), но Эдмонд Карпс O(VE^2), Это основано на предпосылке, что каждый край может быть только критическим O(V) количество раз, и это относится ко всему краю, поэтому мы имеем O(VE) количество раз, когда ребро может стать критическим, т. е. сколько раз может быть найден путь расширения. Это имеет смысл, так как мы можем потратить O(V) количество раз, используя только 1 ребро, а затем, так как нам нужно сделать это для каждого другого ребра в графе, мы получаем O(VE) раз нам нужно найти путь расширения. Тогда BFS принимает O(E)Таким образом, мы получаем нашу окончательную сложность Edmonds Karp по мере необходимости.
Но проблема заключается в следующем: O(VE) аргумент в пользу количества путей расширения является настолько общим, так почему этот анализ не может быть применен к ford fulkerson? Кажется, что сложности двух алгоритмов сравниваются на несправедливой основе. Что именно в алгоритме Эдмондса Карпа делает его превосходным?
Кроме того, почему, когда мы используем подход BFS в Edmonds Karp, мы гарантированно найдем кратчайший путь? Есть ли краткое доказательство этому?