The Max Flow Problem

The next lessons discuss algorithms that solve flow problems in weighted graphs. Apart from direct applications in flow networks, they can also be applied to solve various kinds of matching or assignment problems.

Example of a flow network

As an example, let’s consider the problem of transferring a large file on the internet from London to Frankfurt. We want to achieve the maximum possible throughput in doing so. On the way, we may need to pass several intermediate nodes, and each connection we use on the way has a limited data rate.

This situation can be modeled as a weighted graph where the edge weights correspond to the maximum throughput on each connection, for example,. in Megabit per second: