大流問題的最短增廣路徑算法ppt課件

1、最大流問題的最短增廣途徑算法4114212331s2453t這是初始網絡，加上反向邊這是初始網絡，加上反向邊.4114212331s2453t這是初始網絡和初始殘留網絡這是初始網絡和初始殘留網絡.4114212331s2453t結點標號從此以后將是間隔標號結點標號從此以后將是間隔標號.054321t453s2d(j)是在是在G(f)中的中的j到到t的的最短的間隔的的最短的間隔0221114114212331s2453t弧弧 (i,j) 是是 可進入的，假設可進入的，假設 d(i) = d(j) + 1.054321t453s2一條可進入弧的一條可進入弧的 s-t 途徑是最短途徑途徑是最短途徑.

2、022111可進入弧將表示成粗線可進入弧將表示成粗線.424241121331s2453t運用可進入弧從運用可進入弧從 s 開場進展深度優(yōu)先搜索開場進展深度優(yōu)先搜索.054321t453s2022111下一步下一步. 發(fā)送流并更新殘留容量發(fā)送流并更新殘留容量.21024 2241121331s2453t這里是更新后的殘留容量這里是更新后的殘留容量.054321t453s2022111假設需求，將在以后更新間隔標號假設需求，將在以后更新間隔標號24 2241121331s2453t054321t453s2022111運用可進入弧從運用可進入弧從 s 開場進展深度優(yōu)先搜索開場進展深度優(yōu)先搜索.下一

3、步下一步. 發(fā)送流并更新殘留容量發(fā)送流并更新殘留容量.2102224 224111311s2453t054321t453s2022111這里是更新后的殘留容量這里是更新后的殘留容量.假設需求，將在以后更新間隔標號假設需求，將在以后更新間隔標號2224 224111311s2453t054321t453s2022111運用可進入弧從運用可進入弧從 s 開場進展深度優(yōu)先搜索開場進展深度優(yōu)先搜索.21假設沒有從假設沒有從i出發(fā)的可進入弧，那么出發(fā)的可進入弧，那么relabel(i) 且沿著到且沿著到 i 的的途徑回溯途徑回溯.2224 224111311s2453t054321t45s2022111

4、運用可進入弧從運用可進入弧從 s 開場進展深度優(yōu)先搜索開場進展深度優(yōu)先搜索.21假設沒有從假設沒有從i出發(fā)的可進入弧，那么出發(fā)的可進入弧，那么relabel(i) 且反向沿著從且反向沿著從s出發(fā)的途徑的一條弧出發(fā)的途徑的一條弧.232224 224111311s2453t054321ts2022111運用可進入弧從運用可進入弧從 s 開場進展深度優(yōu)先搜索開場進展深度優(yōu)先搜索.21假設沒有從假設沒有從i出發(fā)的可進入弧，那么出發(fā)的可進入弧，那么relabel(i) 且反向沿著從且反向沿著從s出發(fā)的途徑的一條弧出發(fā)的途徑的一條弧.233s452224 224111311s2453t054321t20

5、22111繼續(xù)從它分開的地方的途徑繼續(xù)從它分開的地方的途徑21假設途徑到達了假設途徑到達了 t, 那么發(fā)送流且更新剩余網絡那么發(fā)送流且更新剩余網絡.233s021452224 223111211s2453t054321t202211121 233s45這是更新后的殘留容量這是更新后的殘留容量.112224 223111211s2453t054321t202211121 233s45搜索從搜索從 s 開場的最短開場的最短 s-t 途徑途徑113231假設沒有從假設沒有從i出發(fā)的可進入弧，那么出發(fā)的可進入弧，那么relabel(i) 且反向沿著從且反向沿著從s出發(fā)的途徑的一條弧出發(fā)的途徑的一條弧.

6、2224 223111211s2453t054321t202211121 233s45搜索從搜索從 s 開場的最短開場的最短 s-t 途徑途徑113231假設沒有從假設沒有從i出發(fā)的可進入弧，那么出發(fā)的可進入弧，那么relabel(i) 且反向沿著從且反向沿著從s出發(fā)的途徑的一條弧出發(fā)的途徑的一條弧.25322224 223111211s2453t054321t02211121 23s45113231 23012235搜索從搜索從 s 開場的最短開場的最短 s-t 途徑途徑假設途徑到達了假設途徑到達了 t, 那么發(fā)送流且更新剩余網絡那么發(fā)送流且更新剩余網絡.2334 12311121s2453

7、t054321t02211121 23s45這是更新了的殘留容量這是更新了的殘留容量11321 232352334 12311121s2453t054321t02211121 23s45搜索最短搜索最短 s-t 途徑途徑11321 232353 40123s1下一步下一步: 更新殘留容量更新殘留容量234221111s2453t054321t02211121 2345這是更新了的殘留容量這是更新了的殘留容量2221 232353 41s1234221111s2453t054321t02211121 2345更新間隔標號和途徑更新間隔標號和途徑2221 232353 41s1234假設假設 d(s) n-1, 那么沒有從那么沒有從s到到 t的途徑