CODEWITHSUNDEEP
algorithmgraph-algorithmmax-flowedmonds-karp
Justin Li
Justin Li

Reputation: 1095

Max flow in unweighted graph

Max flow problem is usually solved by edmond-karp algorithm, which is building residual graph, and using BFS to find augmenting paths.

But usually max flow problem is defined for weighted graph. For unweighted graph, we can simply treat the weight of each edge as 1, but I wonder if there is any simpler algorithm to solve the unweighted version.

Upvotes: 5

Views: 1102

Answers (1)

wookie919
wookie919

Reputation: 3134

Usually people refer to edge "capacities" when talking about flow problems, and "weights/costs" when talking about distance related problems. This causes less confusion.

To rephrase your question, does there exist a simpler algorithm for the max flow problem when every edge has the capacity of 1?

It really depends on what you mean by "simpler", but you can use Ford-Fulkerson algorithm to solve this special case in O(VE) time bound, which is much faster than solving it with the aforementioned Edmonds-Karp algorithm with the time bound of O(VE^2).

Upvotes: 1

Related Questions