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 formulation as an LP model
Torget function 1:
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.
