Cost minimal maximum flow in graphs: Ford-Fulkerson 4: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
Oender (Diskussion | Beiträge) |
Oender (Diskussion | Beiträge) |
||
Zeile 22: | Zeile 22: | ||
Side condition 1:[[Datei:Nebenbedingung 3.png]] | Side condition 1:[[Datei:Nebenbedingung 3.png]] | ||
+ | |||
+ | |||
+ | ---- | ||
+ | '''Example''' |
Version vom 1. Juli 2013, 17:44 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
Torget function 1:
Example