CODEWITHSUNDEEP
algorithm
tv2k18
tv2k18

Reputation: 39

Which is the best algorithm to use out of dincis algorithm and ford fulkerson to solve max flow problems?

Out of these algorithms which will be the best efficient algorithm to solve max flow problems

Upvotes: 2

Views: 2179

Answers (1)

ivangalbans
ivangalbans

Reputation: 500

Which is the best algorithm to use to solve max flow problems?

Answer is: it depends...

Without any information about the graph you have:

  • Ford–Fulkerson algorithm O(f*E)
  • Edmonds–Karp algorithm O(V*E^2)
  • Dinic's algorithm O(V^2*E) but very fast in practice

You must choose which one to use depending on the memory and time constraints of the problem.

V: the number of vertex in the graph

E: the number of edges in the graph

f: is the maximum flow in the graph

Bipartite Graph

Also, if it is a bipartite graph your implementation can be O(n*m)

n: the cardinality of set A

m: the cardinality of set B

Competitive Programming:

In competitive programming Dinic's algorithm is one of the most useful because is very fast in practice. Many of the problems I solved were using Dinic. Although if the restrictions of the problem are not strong implement Ford–Fulkerson algorithm or Edmonds–Karp algorithm is faster than Dinic's algorithm (the time of coding is important too)

Upvotes: 4

Related Questions