Lab 6 - Maximum network flow

The Goldberg-Tarjan algorithm is a method for finding the maximum flow in a network. To explain this to a monkey, let's use the analogy of a river.

Imagine a river with different channels that lead to different locations. Each channel has a maximum amount of water that can flow through it. However, some channels may be blocked, and the water cannot pass through them.

Now, let's say that you want to know the maximum amount of water that can flow from the source of the river to the destination. To do this, you need to find a path from the source to the destination that allows the maximum amount of water to flow through it.

The Goldberg-Tarjan algorithm works by repeatedly finding a path from the source to the destination that allows the most water to flow through it. It does this by assigning a "flow" value to each channel, representing the amount of water that can flow through it.

Initially, all channels have a flow of 0. Then, the algorithm repeatedly finds a path from the source to the destination using channels that have available flow. The available flow is the difference between the channel's maximum flow and its current flow.

Once a path is found, the algorithm determines the maximum amount of water that can flow through the path and updates the flow values for each channel along the path accordingly. This process is repeated until no more paths can be found.

Eventually, the algorithm will find the path that allows the maximum amount of water to flow from the source to the destination. This path represents the maximum flow in the network.

In summary, the Goldberg-Tarjan algorithm finds the maximum flow in a network by repeatedly finding the path that allows the most water to flow through it, updating the flow values for each channel along the path, and repeating the process until the maximum flow is found.