文件名称：在残留图中会出现负环路吗？-最小费用流问题
文件大小：354KB
文件格式：PPT
更新时间：2024-05-16 03:01:17
最小费用流
在残留图中会出现负环路吗？ 假设沿着路径P增广后，在残留图中会出现一个负费用环路W，而在增广之前，不存在负环路。这意味着在路径P中存在一条边（或一个子路径 (i,…,j) ），它的反向边 (j, i) 在增广后会闭合负环路W。我们用cost[j,i]表示边(j,i)的费用，显然为负； cost[W]表示环上除边(j,i)以外的路径的费用，它可正，可负，但因为整个环的费用为负，那么一定有： cost[j,i]+cost[W]<0，那么 cost[w]< -cost[j,i] 因为-cost[j,i] = cost[i,j],则有： cost[w] < cost[i,j]. 显然, 我们可以选择另一条路径从s到t的路径：s->i->W->j->t,那么这条路径的费用要小于P。这就与P是在本次增广过程中寻找到的最短路相矛盾。 这就证明了在残留图中不会出现负环路的情况