O'Reilly logo

Python Algorithms: Mastering Basic Algorithms in the Python Language by Magnus Lie Hetland

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 10. Matchings, Cuts, and Flows

 

A joyful life is an individual creation that cannot be copied from a recipe.

 
 --Mihaly Csikszentmihalyi, Flow: The Psychology of Optimal Experience

While the previous chapter gave you several algorithms for a single problem, this chapter describes a single algorithm with many variations and applications. The core problem is that of finding maximum flow in a network, and the main solution strategy I'll be using is the augmenting path method of Ford and Fulkerson. Before tackling the full problem, I'll guide you through two simpler problems, which are basically special cases (they're easily reduced to maximum flow). These problems, bipartite matching and disjoint paths, have many applications themselves and ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required