Cost minimal maximum flow in graphs: Ford-Fulkerson 4
Basics of the concept
One of the most important application of the Graph-theory is to compute the maximum flow with the restriction of the cost minimization. The difference to the Dijkstra-algorithm and the Floyd-algorithm is the addition of the capacity limitation, which means you have a certain amount of capacity per path that can be used. With this algorithm you are able to determine the maximum flow with the minimum cost from the source (start node) to the sink (end node). In order to achieve this goal you have to find the beneficial path from the source to the sink. Therefore, you have to use the Dijkstra-algorithm. By using this path you lead the maximum possible quantity, which is dictated by the capacity restriction of the path to the sink. This operation is repeated with the next best beneficial path until there is no more paths from the source to the sink left. The total cost is the sum of the product of the amount and the price of every single step.
Mathematical model
Torget function 1:Edges i,j
costs cij
capacity kij
fij flow
i = s start node (source)
j = z end node (sink)
Example
In order to find the cheapest and the shortest way you have to consider the facts that every path has its own price and limited capacity. You can find this information on the tables near the blue arrows. The first number stands for the price and the second number for the available capacity.
The table next to the points A, B, C and D contains the facts of the previous node (first cell), the cumulative price (second node) and the maximum capacity.
The first stage has to be made with the Dijkstra-Algorithm in order to produce the cheapest way. In our example above you can try to get from point A to B and C. The graph shows that the better path is the one between A and B by costing 12 units. Therefore, the other paths can be crossed of. The next path is the one between C and B with an amount of 4 units. After that comes the path between B and D. At the sink you have to cumulate all the prices for the path, which should show the final price for the whole path. Also the capacity is important to be shown. This is possible as shown with the last cell in the table of the nodes, where the maximum is the minimum of the used path. In our example it is 3 units. This amount has to be noted in every table next to the blue paths all the way back up to the source A. In every unused path you note a zero. By doing that it is able to know how much capacity is still available. The capacity between B and C is also marked with an arrow to know in which direction it goes. The reason will be clear in the other steps. Here the capacity of the path B to D is fully exhausted.
The second diagram shows that the capacity between B and D is exhausted. So you have to opt to search for the next better path. In our example it would be A-C-D. And like in the first stage you have to note the price and the availability of the capacity in every path and node. After the second stage the capacity of the path between A and C is also exhausted.
In the third stage the best path is A-B-C-D. But at this stage you have to subtract the cost between B and C from the total costs. This is because there are already remaining units on the node C from the previous stages, and therefore, there is no need spend more money.
In the table above that shows the capacity next to the blue path the maximum amount of units are 3 and that is because there were already 3 units remaining there from the previous stages on C. So the sum of the capacity between B and C is 0.
The last best path is also the path A-B-C-D. But the difference between the third and the fourth step is that the costs in stage 4 are higher because now there are costs between B and C. The minimum capacity is 2 in this stage because the available capacity between C and D is exhausted.
In the last stage you should demonstrate how much the costs of every paths are. Therefore, the following table can be utilized for the summary.
