图论动画最短增广路径算法

1、15.082 和和 6.855J 最大流问题的最短增广路径算法最大流问题的最短增广路径算法2最短增广路径最短增广路径4114212331s2453t这是初始网络，加上弧的反向这是初始网络，加上弧的反向.3最短增广路径最短增广路径4114212331s2453t这是初始网络和初始剩余网络这是初始网络和初始剩余网络.4初始化距离初始化距离4114212331s2453t结点标号从此以后将是距离标号结点标号从此以后将是距离标号.054321t453s2d(j)是在是在G(x)中的中的j到到t的的最大的距离的的最大的距离0221115可进入弧的表示可进入弧的表示4114212331s2453t弧弧 (

2、i,j) 是是 可进入的可进入的，如果，如果 d(i) = d(j) + 1.054321t453s2一条可进入弧的一条可进入弧的 s-t 路径是最短路径路径是最短路径.022111可进入弧将表示成粗线可进入弧将表示成粗线.64242寻找最短寻找最短 s-t 路径路径41121331s2453t使用可进入弧从使用可进入弧从 s 开始进行深度优先搜索开始进行深度优先搜索.054321t453s2022111下一步下一步. 发送流并更新剩余容量发送流并更新剩余容量.210724 22更新剩余容量更新剩余容量41121331s2453t这里是更新的剩余容量这里是更新的剩余容量.054321t453s

3、2022111我们将会以后更新距离标号，如果需要我们将会以后更新距离标号，如果需要.824 22寻找最短寻找最短 s-t 路径路径41121331s2453t054321t453s2022111使用可进入弧从使用可进入弧从 s 开始进行深度优先搜索开始进行深度优先搜索.下一步下一步. 发送流并更新剩余容量发送流并更新剩余容量.21092224 22更新剩余容量更新剩余容量4111311s2453t054321t453s2022111这里是更新的剩余容量这里是更新的剩余容量.我们将会以后更新距离标号，如果需要我们将会以后更新距离标号，如果需要.102224 22寻找最短寻找最短 s-t 路径路径

4、4111311s2453t054321t453s2022111使用可进入弧从使用可进入弧从 s 开始进行深度优先搜索开始进行深度优先搜索.21如果没有从如果没有从i出发的可进入弧，那么出发的可进入弧，那么relabel(i) 且沿着到且沿着到 i 的的路径反向路径反向.112224 22更新距离和路径更新距离和路径4111311s2453t054321t45s2022111使用可进入弧从使用可进入弧从 s 开始进行深度优先搜索开始进行深度优先搜索.21如果没有从如果没有从i出发的可进入弧，那么出发的可进入弧，那么relabel(i) 且反向沿着从且反向沿着从s出发的路径的一条弧出发的路径的一条

5、弧.23122224 22更新距离和路径更新距离和路径4111311s2453t054321ts2022111使用可进入弧从使用可进入弧从 s 开始进行深度优先搜索开始进行深度优先搜索.21如果没有从如果没有从i出发的可进入弧，那么出发的可进入弧，那么relabel(i) 且反向沿着从且反向沿着从s出发的路径的一条弧出发的路径的一条弧.233s45132224 22寻找最短寻找最短 s-t 路径路径4111311s2453t054321t2022111继续从它离开的地方的路径继续从它离开的地方的路径21如果路径达到了如果路径达到了 t, 那么发送流且更新剩余网络那么发送流且更新剩余网络.233

6、s02145142224 22更新剩余容量更新剩余容量3111211s2453t054321t202211121 233s45这是更新的剩余容量这是更新的剩余容量.11152224 22搜索最短搜索最短s-t 路径路径3111211s2453t054321t202211121 233s45搜索搜索从从 s 开始的开始的最短最短 s-t 路径路径113231如果没有从如果没有从i出发的可进入弧，那么出发的可进入弧，那么relabel(i) 且反向沿着从且反向沿着从s出发的路径的一条弧出发的路径的一条弧.162224 22搜索最短搜索最短s-t 路径路径3111211s2453t054321t20

7、2211121 233s45搜索从搜索从 s 开始的最短开始的最短 s-t 路径路径113231如果没有从如果没有从i出发的可进入弧，那么出发的可进入弧，那么relabel(i) 且反向沿着从且反向沿着从s出发的路径的一条弧出发的路径的一条弧.2532172224 22搜索最短搜索最短s-t 路径路径3111211s2453t054321t02211121 23s45113231 23012235搜索从搜索从 s 开始的最短开始的最短 s-t 路径路径如果路径达到了如果路径达到了 t, 那么发送流且更新剩余网络那么发送流且更新剩余网络.182334 12更新剩余容量更新剩余容量311121s2

8、453t054321t02211121 23s45这是更新了的剩余容量这是更新了的剩余容量11321 23235192334 12搜索最短搜索最短s-t 路径路径311121s2453t054321t02211121 23s45搜索最短搜索最短 s-t 路径路径11321 232353 40123s1下一步下一步: 更新剩余容量更新剩余容量202342更新剩余容量更新剩余容量21111s2453t054321t02211121 2345这是更新了的剩余容量这是更新了的剩余容量2221 232353 41s1212342搜索最短搜索最短s-t 路径路径21111s2453t054321t02211121 2345更新距离标号和路径更新距离标号和路径2221 232353 41s1234如果如果 d(s) n-1, 那么没有从那么没有从s到到 t的路径的路径456522