Max-flow min-cut algorithm

Aside from shortest paths and routes, transportation logistics sometimes involve city planning to plan, say, roadwork with the least interruption to traffic patterns or supply chains. The goal is to maximize traffic flow through points of interest (say, major intersections or buildings with high volumes of visitors/workers each day) while minimizing which routes are cut off.

In graph theory, the max-flow min-cut algorithm seeks to partition a network to maximize the flow of information through a social network, the flow of traffic in a transportation network, or the flow of material through an electrical or water pipeline network, among others. Typically, there’s a starting vertex and an ending vertex with respect to flow, though it is possible to run the algorithm through all possible combinations and aggregate results to maximize flow for the entire network.

Let’s consider the example of traffic flow from a dense residential area outside...