Graph Theory37 sections · 1633 units
Open in Course

Faster Algorithms

(Beyond Edmonds-Karp)

Edmonds-Karp is not the fastest. Dinic's algorithm runs in O(V2E)O(V^2 E) time. Push-relabel algorithms can achieve O(V3)O(V^3) or better. For competitive programming, Edmonds-Karp is usually fast enough unless VV and EE are huge (over 1010,000000).

Dinic's is faster but more complex to code. If time limits are tight, consider Dinic's. Otherwise, stick with Edmonds-Karp. It is simpler and less bug-prone. Know when the extra complexity is worth it.

Space complexity is O(V+E)O(V + E) for the data structures used.