发布时间 : 星期六 文章基于预流推进的最小标号最大流算法更新完毕开始阅读9bd60880fd4ffe4733687e21af45b307e971f90c
尽管它的理论复杂度很低。经研究发现，节点组之间的距离标号差距越大，在回溯过程中盈余流量反复推进的次数则越多，因此可以通过适当调整距离标号大小减少回溯时间。如，重新定义发点s的距离，在原始预流推进算法中，s点的距离为n（n表示网络中节点总数），而在应用过程中，可以将s点距离定义为max{d（i）|i∈G（V）＼（s，t）}+1，该做法不影响距离标号的有效性。仿真实验验证了在上千节点的大规模网络中执行该操作的必要性，否则回溯过程执行时间是难以接受的。 4基于预流推进的最小标号最大流算法
4.1最小标号和增加的终止准则
本文提出的基于预流推进的最小标号最大流算法是一种贪心算法，有别于最高标号预流推进算法，它在选取活跃节点时遵循优先选取最低位势盈余点规则，即一旦发现了最小标号活跃节点，就立即执行一次流量推进，在允许弧条件的限制下，若推进过程中节点位势不发生改变，盈余将沿着距离标号下降方向进行最终推进至收点t。贪心算法虽然会导致推进过程承受最频繁的活跃节点更新，但是能保证在回溯现象发生之前将所有流量推送至收点t，若没有出现回溯现象，则在最后一个活跃节点变为非活跃节点后，终止算法；若出现回溯现象，则说明流量输送过程已执行，此时也应当终止算法。因此，该算法的终止条件有两个：第一个是预流
推进算法框架中的终止条件，即不存在活跃节点；另一个是新定义的终止条件，即回溯现象发生，这两个终止条件任意一个被触发，都应执行退出命令。新定义的终止条件无法应用于最高标号预流推进算法，因为它不能在回溯现象发生时完成所有的流量推进，列队预流推进和一般预流推进算法亦是如此。
4.2最小标号预流推进算法终止条件的可行性分析 推论1在最小标号规则下，任意一次推进过程的步骤数不超过2n。
证明 执行活跃的节点流量推进时，分为两种情况：第一种情况为，流量将完整或部分推进至收点t；另一种情况为，在遇到位势变化时，流量在非最小标号节点上盈余，则在下一步中选择另一个最低位势活跃节点并重新进行流量推进。在第一种情况下，执行流量推进时最多经过n-2个节点，亦最多经过n-2次距离标号调整，因此不超过2n-4步。在第二种情况下，由于被调整距离标号的节点位势升高，因而不会被再次选取或重复经过，设流量更换过程执行了k步，则流量更换过程执行不超过2k步，余下的推进过程至多执行n-k-2步，故加上距离标号调整过程总步骤不超过2n-4步，若已升高位势的节点在一次推进中被重复经过，则说明算法进行至回溯阶段，应当立即终止。在最高标号预流推进算法中，活跃节点位势增高反而会导致被优先选择，因此不能满
足最小标号规则下的推论。
上述推论给出了最小标号预流推进算法的终止条件可行性，同时也定义了这一终止条件：检测收点t的流量变化，若执行2n次流量推进尝试后收点t未得到更新，说明算法进入回溯阶段，应立即终止。 4.3最小标号预流推进算法
本文算法在预流推进算法框架下作了两处设定，第一处是活跃节点的选取方式，第二处是终止条件的改变，算法如下： 程序前
用逆向宽度优先搜索确定网络距离标号d，置d（s）=max{d（j）|j∈G（V）＼s}+1；
对所有节点V={vk|（vs，vk）∈G（M）}执行一次饱和推进；
While （{vk|vk∈G（Active）}≠是两个单独的竖线还是整体的一个软件盘上双竖线，请核实说明，逻辑语言中\表示\或\的含义，是两个单独的\，应该是一个独立的整体‖
excesst（current）>excesst（current-2n）） {
在收点t盈余未发生变化时计数器+1，否则置计数器为0；
选取活跃节点vi=min{d（vk）|vk∈G（Active）}； 选取节点V={vk|d（i）=d（k）+1}； If （V！=） {
While（vj！=NULL） {
选取vj∈V； V=V＼vj；
flow=min{c（i， j），excessi}； c（i， j）=c（i， j）-flow； c（j，i）=c（j，i）+flow； excessi=excessi-flow； If （excessi==0） Break； } }
If （V==‖excessi>0）
d（i）=min{d（j）+1|（i， j）∈ }
flow=excesst 程序后
4.4算法复杂度分析
G（M）}；