Computer scienceAlgorithms and Data StructuresAlgorithmsGraph algorithmsMaximum flow algorithms

Cycle-cancelling algorithm

Counting the gain

Report a typo

Imagine that you have the following graphs: a flow network (on the left) and a weighted graph, representing the costs of going through an edge. Certain flow has already been found in a network, so the graphs look like this:

On the left: a flow network, containing information about the flow and capacity of each edge. On the right: a graph, containing information about the costs of going through each edge.

By how many units can the cost of the maximum flow be reduced?

Enter a number

___

Create a free account to access the full topic