mpm算法求最大流解析

mpm算法求最大流解析MPM算法（ModifiedPush-RelabelMethod，改进的压入-重标记算法）是求解网络最大流问题的高效算法之一，其核心是在经典“压入-重标记算法”基础上优化了“活跃节点选择策略”，通过优先处理高度最高的活跃节点，减少无效操作，大幅提升效率。以下从基础概念、算法步骤、示例演示到复杂度分析进行全面解析。一、前置基础：网络流与核心概念在讲解算法前，需明确网络流的基本术语（后续算法步骤将直接沿用）：流网络：一个有向图

G=(V,E)，包含：源点

s（唯一入度为0的节点，流量起点）；汇点

t（唯一出度为0的节点，流量终点）；每条边

(u,v)

有“容量”

c(u,v)≥0（最大可通过流量），“流量”

f(u,v)≤c(u,v)（实际通过流量）。可行流：满足以下条件的流量分配：容量约束：对所有边

(u,v)，0≤f(u,v)≤c(u,v)；流量守恒：对所有非源非汇节点

u，流入流量=流出流量（∑v​f(v,u)=∑v​f(u,v)）。最大流：总流量（从

s

流出的总流量）最大的可行流。残量网络：对原网络的“剩余容量”描述，每条边

(u,v)

的“残量容量”

r(u,v)=c(u,v)−f(u,v)；若

f(u,v)>0，则存在“反向边”

(v,u)，残量容量

r(v,u)=f(u,v)（用于“流量回退”，修正无效分配）。高度函数（压入-重标记算法核心）：给每个节点

u

分配高度

h(u)，满足：h(s)=∣V∣，h(t)=0，对残量网络中每条边

(u,v)，h(u)≤h(v)+1（保证流量“向汇点方向流动”，避免循环）。余流：对节点

u，余流

e(u)=∑v​f(v,u)−∑v​f(u,v)（流入-流出的超额流量）；若

e(u)>0

且

u=s,t，则

u

为“活跃节点”（需处理超额流量）。二、MPM算法的核心思想经典“压入-重标记算法”的瓶颈是：随机选择活跃节点处理时，可能频繁对低高度节点操作，导致无效重标记（反复提升高度却无法压出流量）。MPM算法的改进：每次优先选择高度最高的活跃节点进行处理。

理由：高度最高的节点离“汇点方向”更近（高度函数特性），其超额流量更可能通过残量边直接压向低高度节点（甚至最终流向汇点），减少“流量回退”和无效重标记，提升效率。三、MPM算法的详细步骤步骤1：初始化（构建残量网络+初始化高度与余流）初始流量：所有边流量

f(u,v)=0，残量容量

r(u,v)=c(u,v)（反向边残量为0）。高度初始化：源点高度

h(s)=n（n=∣V∣，确保源点可向所有节点压流）；其他节点高度

h(u)=0。余流初始化：源点向所有相邻节点“饱和压流”：对

(s,v)∈E，令

f(s,v)=c(s,v)，则

e(v)=c(s,v)（v

获得超额流量），e(s)=−∑c(s,v)（源点余流为负，非活跃）；其他节点

e(u)=0。步骤2：处理活跃节点（核心：压入+重标记，优先最高高度）循环执行以下操作，直到无活跃节点（此时余流全为0，流达到最大）：选择活跃节点：从所有活跃节点（e(u)>0,u=s,t）中，选高度最高的节点

u。对节点

u

执行“批量压入”：

遍历

u

的所有相邻节点

v（残量网络中

r(u,v)>0），若

h(u)=h(v)+1（满足“高度差1”，可压流）：压流量

δ=min(e(u),r(u,v))（取节点余流与边残量的最小值，避免超额）；更新流量：f(u,v)+=δ（正向边）或

f(v,u)−=δ（反向边）；更新残量：r(u,v)−=δ，r(v,u)+=δ；更新余流：e(u)−=δ，e(v)+=δ（v

若余流从0变正，成为新活跃节点）。

直到

e(u)=0（超额流量全压出）或无满足条件的

v（无法压流，需重标记）。若仍有超额流量（e(u)>0），执行“重标记”：

找到

u

所有残量边

(u,v)

中，高度最小的

v，令

h(u)=h(v)+1（提升自身高度，使其能向该

v

压流）。步骤3：终止与结果当无活跃节点时，算法终止。此时从源点流出的总流量（∑f(s,v)）即为最大流。四、示例演示：用MPM算法求简单网络最大流以如下流网络为例（节点

s=1,t=4，边容量标注为

c(u,v)）：plaintext1(源)→2，c=3；1→3，c=2；2→4，c=2；2→3，c=2；3→4，c=3；步骤1：初始化残量网络：所有边残量

r(u,v)=c(u,v)（如

r(1,2)=3,r(1,3)=2

等）。高度：h(1)=4（n=4），h(2)=h(3)=h(4)=0。余流：源点向2、3压流后，e(2)=3,e(3)=2（均为活跃节点），e(1)=−5，e(4)=0。步骤2：处理活跃节点（优先最高高度）首次选择：活跃节点2、3的高度均为0（最高），任选2（假设选2）。检查2的相邻节点：4（r(2,4)=2）、3（r(2,3)=2）。高度条件：h(2)=0，需

h(v)=−1（不可能）→无法压流，重标记2：

找2的残量边中

h(v)

最小的v（4和3的h均为0），令

h(2)=0+1=1。再次处理2（仍活跃，h=1）：相邻节点4（h=0）、3（h=0），满足

h(2)=h(v)+1（1=0+1）。向4压流：δ=min(e(2)=3,r(2,4)=2)→2，更新后：r(2,4)=0，e(2)=3−2=1，e(4)=0+2=2（但4是汇点，余流忽略）。向3压流：δ=min(e(2)=1,r(2,3)=2)→1，更新后：r(2,3)=1，e(2)=0（2不再活跃），e(3)=2+1=3（3仍活跃，h=0）。选择活跃节点3（当前唯一活跃，h=0）：相邻节点4（r(3,4)=3）、2（r(3,2)=1，反向边，因之前向3压流产生）。高度条件：h(3)=0，需

h(v)=−1→无法压流，重标记3：

找3的残量边中

h(v)

最小的v（4的h=0，2的h=1），令

h(3)=0+1=1。再次处理3（h=1）：相邻节点4（h=0）满足

h(3)=1=0+1，向4压流：δ=min(e(3)=3,r(3,4)=3)→3，更新后：r(3,4)=0，e(3)=0（3不再活跃），e(4)=2+3=5（汇点余流忽略）。此时无活跃节点，算法终止。总流量=从1流出的流量（3+2=5），与汇点收到的流量（2+3=5）一致，即最大流为5。五、算法复杂度与优势时间复杂度：MPM算法通过优先选择最高高度节点，大幅减少重标记次数（每个节点重标记次数不超过n），总时间复杂度为

O(n3)（n为节点数），优于经典Ford-Fulkerson（O(Fm)，F为最大流值，不稳定）和原始Push-Relabel（O(n2m)）。优势：无需寻找增广路径（区别于Ford-Fulkerson/Dinic），直接通过“压入-重标记”局部调整流量，且通过节点选择策略减少无效操作，适合节点数较多的网络。总结MPM算法的