Maximum Flow Exhaustion of Paths Algorithm

[JonesyMints]

This algorithm doesn't always give the optimal solution, look up Ford-Fulkerson for an algorithm that does. This one's a really useful starting point though.

[1652449]

Thanks. Glad it was helpful.

[gawd0r]

Best explanation I've ever seen of anything. I spent hours trying to understand how this works, now it's explained so beautifully and simple in an animation. Thank you so much!

[ncmglr]

emege saygi +rep

[DaxXx988]

Just a note.

The exhaustion of paths does not always give the optimum result,

i.e. maximum flow is not always the one found with this algorithm.

To get the max flow, you should in the end construct a residual network (with forward and backward arcs) and try to find the so called augmenting paths.

The algorithm is called Flow augmenting path algorithm, and it is optimal.

Thank you for the video!

[EnvyProjekt]

very helpful. Thank you!

[chivaslestlee01]

i love it really it helps me alot in understanding network flow

[kenshiro3007]

What about the path S-U-W-Z-T? Why is the smallest capacity for this path not identified?

[1652449]

@kenshiro3007 Because when identifying the path S-U-W-T , the capacity of of the edge U-W was exhausted. Therefore it couldn't be used any further.

You could choose to use the path S-U-W-Z-T (ie choose to solve the problem using a different order) But this should not effect the end result.

[tomlooway]

can you post a mathematical solution? as in excel with solver or similar?

[Jackpotur]

@tomlooway it's an algorithm