开发者

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 t开发者_C百科he Ford-Fulkerson algorithm.

But how should I handle the case of a multigraph?


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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜