Cost minimal maximum flow in graphs: Ford-Fulkerson 4: Unterschied zwischen den Versionen

Version vom 1. Juli 2013, 17:36 Uhr

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