匈牙利算法的时间复杂度是否优于Edmonds-Karp算法？附MCMF场景疑问

• 匈牙利算法的n取值与复杂度计算错误
  工人-工作匹配属于二分图最小权匹配问题，匈牙利算法的时间复杂度并非基于“工人+工作”的总数计算。针对m个工人、k个工作的场景：

  • 优化版非方阵实现的复杂度为O(min(m²k, k²m))，你的例子中m=2、k=3，复杂度为O(2²×3)=12；
  • 若补为方阵（添加虚拟工人/工作），n取方阵阶数3，复杂度为O(3³)=27，而非你说的5³=125。

• Edmonds-Karp算法的适用场景与复杂度公式错误
  Edmonds-Karp是最大流算法，不是最小费用最大流（MCMF）的标准解法，它的时间复杂度是O(F×E²)，其中F是最大流的流量值（你的例子中最大流为2，因为只有2个工人），而非O(V×E²)。
  解决MCMF问题常用的是基于SPFA的连续最短路增广算法，时间复杂度为O(F×V×E)。

• 流图边数计算不完整
  流图顶点数7的计算是正确的（源点+2个工人+3个工作+汇点），但边数需包含反向边：

  • 正向边共11条（源点到工人2条、工人到工作6条、工作到汇点3条）；
  • 每条正向边对应一条反向边，总边数为22条。结合正确的MCMF复杂度公式，你的例子中复杂度为O(2×7×22)=308，即使仅算正向边也为O(2×7×11)=154，远小于你之前错误计算的847。

内容的提问来源于stack exchange，提问作者Sena