Maximum Flow Exhaustion of Paths Algorithm

Network optimization: Using network diagrams to find optimal solutions to problems. In this video we are looking at an example of a maximum flow type question using the exhaustion of paths algorithm. Please comment if it was helpful.

Category:

Education

Tags:

• Maximum
• Flow
• Exhaustion
• of
• Paths
• Algorithm

[1652449]

Thanks. Glad it was helpful.

[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.

[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.

[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!

[Jackpotur]

@tomlooway it's an algorithm

[EnvyProjekt]

very helpful. Thank you!

[chivaslestlee01]

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