Search code examples
algorithmgraphmax-flow

Maximal flow graph algorithm

Does someone know which algorithm should be used to find the maximal flow in the unoriented graph?

As far as I understand, the unoriented network here basically turns the graph into a multigraph with vertices connected by two "ordinary" ribs and two "fake" ribs, which are, for example used in the Ford-Fulkerson algorithm.

But how should I handle the case of a multigraph?

Solution

  • If you have unoriented edge

         5
* ------ *

    then you can turn it into two oriented edges:

         5
  ------>
*         *
  <------
     5

    Ford-Fulkerson method works on such graphs perfectly.