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 in 1956. Compared to Dijkstra or Floyed algorithm it should find the shortest way in the graph. 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 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 in the graph. You can use for example Djykstra-Algorithm and consider all prices as distances.

If Djykstra finds a way go to STEP 2, otherwise the cost minimal maximum flow has been found and is 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. Djykstra-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.