开发者

Maximal flow graph algorithm

开发者 https://www.devze.com 2023-01-30 18:54 出处:网络
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

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

精彩评论

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