Cost minimal maximum flow in graphs: Ford-Fulkerson 2
Ford –Fulkerson-Algorithm
The Ford-Fulkerson-Algorithm [FFA] belongs to the graph theory and was developed by Lester Randolph Ford and Delbert Ray Fulkerson. Compared to Dijkstra or Floyed algorithm it should find not the shortest way in graphs, the FFA should find the cost minimal maximum flow in a graph. To be able to find the cost minimal maximum flow in a graph from one node to another you need to know the maximal flow and the costs for one unit of flow for every edge.
How FFA works should be explained with a pseydo-algorithm:
Var: K=0 (costs)
STEP 1: Find the cheapest way fron the start node to the destination node in the graph. You can use for example Dijkstra-Algorithm and consider all prices as distances.
If Dijkstra finds a way go to STEP 2, otherwise print K.
STEP 2: Find out the maximal flow for this way. It is constrained by the minimum of the maximal possible flow for the corresponding edges. K = K + “sum of the costs from the path” * “transported units”. The maximal flow of each used edge has to be reduced about the transported units. If for one or more edges the maximal flow returns to zero, the corresponding costs have to be set to infinity. Dijkstra-Algorithm can’t use these edges anymore. Return to STEP 1.
Example:
Imagine the situation that a firm wants to transport products from one plant to another. The trucks can drive on different highways. For each highway you have to pay tolls in different heights. Each highway has a different capacity. The costs of the trucks can be neglected. Your job is to find the maximum possible flow with minimal costs.
You can see five cities connected with highways. Your start is City A, destination City E. For each highway f describes the maximum flow and p the price for one unit of flow. Now Dijkstra has to find the cheapest (remember: consider the prices as distances) way from the start to the destination:
Dijkstra found the cheapest way: A --> B --> E with costs of 10 per unit. The maximum possible flow is 5 units, limited by AB and BE. There is no more possible flow on this highway, the costs are set to infinity, the values of the maximal possible flow are updated. Dijkstra has to find the new cheapest way:
In the picture you can see the new cheapest way A --> C --> E. The way from step 1 is marked grey because there is no possibility of transportation anymore. On the new way the maximal flow is constrained by the highway CE, the costs are set to infinity. 10 Units are transported from A to E. Now the next can be started. Dijkastra has to find the new cheapest way.
There is only one highway from A left. This route limits the system with its maximum still possible flow = 10:
There is no flow possible anymore. In our pseudo-algorithm dijkstra will try to find the new cheapest way. The algorithm will end with printing out K. If you do the FFA by Hand, you can skip this last Dijkstra-Algorithm.
In the following table K is calculated:
In the table you can see the maximal possible flow = 30 and K (summed costs)
Additional
You can find out the maximum possible flow with the min cut max flow theorem. This is shown in the following picture:
--fwschmid (Diskussion) 17:45, 26. Jun. 2013 (CEST)
