Content deleted Content added
m Robot-assisted disambiguation Graph |
m Fixed termination condition (F-F always terminates, but might do so very slowly with large weights) |
||
Line 1:
In [[computer science]], in the field of [[graph theory]], the '''Edmonds-Karp algorithm''' is an implementation of the ''[[Ford-Fulkerson algorithm]]''. The important additional feature is that the shortest augmenting path is used at each step, which guarantees that the computation will terminate in polynomial time. In most implementations, the shortest augmenting path is found using [[breadth-first search]].
The Edmonds-Karp algorithm [[Big O notation|runs]] in O(VE<sup>2</sup>) time, where V and E is the number of vertices and edges in a [[graph theory|graph]], respectively.
| |||