最大流算法及其应用new

《最大流算法及其应用new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据最大流算法及其应用张永军淮阴工学院223001斌誊鬟

2、、

3、薯

4、≮_

5、。i?j薯?

6、j毫。本文介绍了图论中最大流问题的算法，：-1

7、“_■

8、一j“。

9、童并且讨论Ford-Fulkerson等算法在解决实际问题中的应丽。懑§鸯链濑；警≮誊≮鍪％譬薹譬蠢鬻譬鏊漤”u囊誊誉誊鬻攀i鬣摹誊薹

10、?萋耄。囊嚣誊蕊毒二萋最走漉算涤；Ford-Fulkerson方法；Push-relabel雾汝渗鹣舔i确鏊篱i鞲i鏊§囊攀《警甏霎蛰甍§攀《{篱；§《《

11、§毯ll饕誊

12、毯藩≤

13、鬻l鬻鍪甏《誊；罄簿秀孽誊《蛔thispaperMaximumFlowAtgori

14、'thmofgraphytheoryisintroduced，and％heapplicationsofFord-FulkersonalgorithmetctosolveteaIproblem．峨辆罐i囊骥誉蕤鬻鬻囊i萋攀蘩霪鬟鬻囊鬻篱攀鬟霪鬻鬈囊鬻黧?萋MaximumFlowAlgorithm：Ford～FulkersonAlgorithm：Push-rela№lalgorithms1前言在现实生活中，我们会遇到很多复杂的问题，我们希望用一种巧妙的办法去简化它，优化它和解决它，图就是一个有效的工具。把实际问题化为图后，我们能清楚地观察到整个局面，

15、方便我们进行具体分析。所以研究和总结图的应用算法是件有意义且必要的事情。图论的问题基本上有两大类，一是存在性问题，一是最优化问题。图论是一种较为直接明了的算法，此外图论涵盖的范围很广，内容也很丰富，单就学术方面而言，已有很大的发展空间和研究价值。在Et常生活中，我们经常可以找到与图论息息相关的内容，利用图论我们可以更有效地解决问题。2最大流算法最大流问题就是在某种网络中以最好的方式将一些东西从一个地方运到另外一个地方。更具体一点地说，这个问题的起因和1950年苏维埃共和国的铁路线路有关。美国想要知道苏维埃共和国通过铁路线路能够多快从东欧的国家得至

16、峙p给。除此之外，美国还想知道哪个线路能够最容易地被破坏来切断到苏维埃的救援。事实证明这两个问题密切相关，并且解决最大流问题同时也就解决了计算最经济的切断苏维埃救援的最小割问题。2．1TheFord—FulkersonAlgorithmFord—FulkersonMethod是用来解maximum—flow问题的方法，为何不说是Ford—Fulkersonalgorithm，其理由为这个Ford—Fulkerson所想出的方法是包含许多种不同跑出来的结果，并不是单一的结果。Ford—FulkersonAlgorithm包含了三大重要的想法，分别为

17、Residualnetworksaugmentingpathsandcuts，最主要的是利用Residuenetwork的观点来找出maximumflow。以下为此方法的内容：Ford-FulkersonAlgorithm(G，s，t)linitializeflowfto02whilethereexistsanaugmentingpathP3doaugmentflowfalongP4returnf用更详细的写法则为Ford-Fulkerson(G，S，t){foreachedge(u，V)∈EIG]doIIu，v]?0fly，ul?0whiJe?

18、pathPfromStotOnGfdocf(p)?min{cf(u，v)：(u，v)isinP}fOreach(u，v)inPdof[u，v]?flu，v]+c“p)f[v，u]?一Ilu，v]returnfJ其中的augmentingpathP可将其想像成一条从SourceS到sinkt的路径P，此方法是回递式的，首先令f(u，v)=0，Vu，蚝V然后再每次递归中找出一条augmentingpath来增JTNf的流量，然后沿着这条路径继续去augmentflow的值，一直重复到我们找万方数据不到任何的augmentpath为止，我们就可找到最大

19、流量的路径。Edmonds—Karp算法使用BFS来找augmentpath，之所以能称为Edmonds-Karpalgorithm，因为其timecomplexity为单一0(VE‘2)，如果是发生下面那个情形，如果单纯的使用Ford—FulkersonAlgorithm找augmentpath就会要执行2M个iteration才能做完。2．2Push—relabelalgorithms除了上述提到的方法可以算出最大流量问题的解外，在这一小节我们要提供另一种同样是解最大流量问题的算法一Push—relabelaigorithms。Pushrel

20、abel用到一个很有趣的概念--Preflow他允许流进的量比流出的量还要多，有水来就先流进来，流不出去再说。Push—relabel算