4

Is there any variation of the Ford-Fulkerson that adds an extra dimension of "weight" to the edges?

By that, I mean some edges are more ideal than others, and while all the possibilities are there, it will prioritize the ideal edges over the lesser ideal edges.

Leah Sapan
  • 3,621
  • 7
  • 33
  • 57
  • I don't see the point here. Ford-Fulkerson calculates a maximum flow. You can think of the network as series of pipes of different diameters. How much water flows through the pipes? FF answers that question. Other than diameter, no pipe is "more ideal" than any other pipe. – Tyler Durden May 26 '13 at 18:21
  • The reason I ask is I am using this algorithm to do the typical assignment of jobs problem. However, I would like to incorporate the possibility of trainings as opposed to just leaving jobs blank if no one is trained for that position. – Leah Sapan May 26 '13 at 19:19
  • 1
    If you are matching jobs to people, then you are solving an assignment problem, which is solved by the Hungarian algorithm. – Tyler Durden May 26 '13 at 19:23
  • Thank you Tyler, I actually ended up implementing it using the Hungarian algorithm found http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm – Leah Sapan May 27 '13 at 05:27

1 Answers1

3

There are two common generalisations that I know of to add weights.

Min cost flow

Suppose you had a weight for each edge and wanted to compute the flow that satisfied the constraints and had minimum cost. (Cost = sum of weight * units flowing along associated edge)

This problem is called minimum cost flow.

An implementation can be found in networkx called min-cost-flow.

Here is a good topcoder tutorial on a primal-dual approach.

My favorite algorithm for this was actually invented by Fulkerson himself in 1961 and is called the out of kilter algorithm.

Max flow min cost

Suppose you definitely wanted the maximum flow, but wanted to choose the flow with least weight.

This differs from the first interpretation, in that a min-cost-flow may not give the maximum possible flow. For example, suppose we have a single edge start->end with the constraint that the flow is in the range 0 to 1, and a weight of 1.

The min-cost-flow will be a flow of 0, while the max-flow-min-cost will have a flow of 1.

An implementation for this can be found in networkx called max_flow_min_cost.

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
  • Thanks so much! Max flow min cost is the solution to my problem. Tyler's suggestion for the hungarian algorithm also works very well. – Leah Sapan May 26 '13 at 20:28