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

1、最大流問題的最短增廣路徑算法24114212331s2453t這是初始網(wǎng)絡(luò)，加上反向邊這是初始網(wǎng)絡(luò)，加上反向邊.34114212331s2453t這是初始網(wǎng)絡(luò)和初始?xì)埩艟W(wǎng)絡(luò)這是初始網(wǎng)絡(luò)和初始?xì)埩艟W(wǎng)絡(luò).44114212331s2453t結(jié)點(diǎn)標(biāo)號從此以后將是距離標(biāo)號結(jié)點(diǎn)標(biāo)號從此以后將是距離標(biāo)號.054321t453s2d(j)是在是在G(f)中的中的j到到t的的最短的距離的的最短的距離02211154114212331s2453t弧弧 (i,j) 是是 可進(jìn)入的，假設(shè)可進(jìn)入的，假設(shè) d(i) = d(j) + 1.054321t453s2一條可進(jìn)入弧的一條可進(jìn)入弧的 s-t 路徑是最短路徑路徑是最

2、短路徑.022111可進(jìn)入弧將表示成粗線可進(jìn)入弧將表示成粗線.6424241121331s2453t使用可進(jìn)入弧從使用可進(jìn)入弧從 s 開始進(jìn)行深度優(yōu)先搜索開始進(jìn)行深度優(yōu)先搜索.054321t453s2022111下一步下一步. 發(fā)送流并更新殘留容量發(fā)送流并更新殘留容量.210724 2241121331s2453t這里是更新后的殘留容量這里是更新后的殘留容量.054321t453s2022111如果需要，將在以后更新距離標(biāo)號如果需要，將在以后更新距離標(biāo)號824 2241121331s2453t054321t453s2022111使用可進(jìn)入弧從使用可進(jìn)入弧從 s 開始進(jìn)行深度優(yōu)先搜索開始進(jìn)行深度

3、優(yōu)先搜索.下一步下一步. 發(fā)送流并更新殘留容量發(fā)送流并更新殘留容量.21092224 224111311s2453t054321t453s2022111這里是更新后的殘留容量這里是更新后的殘留容量.如果需要，將在以后更新距離標(biāo)號如果需要，將在以后更新距離標(biāo)號102224 224111311s2453t054321t453s2022111使用可進(jìn)入弧從使用可進(jìn)入弧從 s 開始進(jìn)行深度優(yōu)先搜索開始進(jìn)行深度優(yōu)先搜索.21如果沒有從如果沒有從i出發(fā)的可進(jìn)入弧，那么出發(fā)的可進(jìn)入弧，那么relabel(i) 且沿著到且沿著到 i 的的路徑回溯路徑回溯.112224 224111311s2453t05432

4、1t45s2022111使用可進(jìn)入弧從使用可進(jìn)入弧從 s 開始進(jìn)行深度優(yōu)先搜索開始進(jìn)行深度優(yōu)先搜索.21如果沒有從如果沒有從i出發(fā)的可進(jìn)入弧，那么出發(fā)的可進(jìn)入弧，那么relabel(i) 且反向沿著從且反向沿著從s出發(fā)的路徑的一條弧出發(fā)的路徑的一條弧.23122224 224111311s2453t054321ts2022111使用可進(jìn)入弧從使用可進(jìn)入弧從 s 開始進(jìn)行深度優(yōu)先搜索開始進(jìn)行深度優(yōu)先搜索.21如果沒有從如果沒有從i出發(fā)的可進(jìn)入弧，那么出發(fā)的可進(jìn)入弧，那么relabel(i) 且反向沿著從且反向沿著從s出發(fā)的路徑的一條弧出發(fā)的路徑的一條弧.233s45132224 22411131

5、1s2453t054321t2022111繼續(xù)從它離開的地方的路徑繼續(xù)從它離開的地方的路徑21如果路徑達(dá)到了如果路徑達(dá)到了 t, 那么發(fā)送流且更新剩余網(wǎng)絡(luò)那么發(fā)送流且更新剩余網(wǎng)絡(luò).233s02145142224 223111211s2453t054321t202211121 233s45這是更新后的殘留容量這是更新后的殘留容量.11152224 223111211s2453t054321t202211121 233s45搜索從搜索從 s 開始的最短開始的最短 s-t 途徑途徑113231如果沒有從如果沒有從i出發(fā)的可進(jìn)入弧，那么出發(fā)的可進(jìn)入弧，那么relabel(i) 且反向沿著從且反向沿著從

6、s出發(fā)的路徑的一條弧出發(fā)的路徑的一條弧.162224 223111211s2453t054321t202211121 233s45搜索從搜索從 s 開始的最短開始的最短 s-t 途徑途徑113231如果沒有從如果沒有從i出發(fā)的可進(jìn)入弧，那么出發(fā)的可進(jìn)入弧，那么relabel(i) 且反向沿著從且反向沿著從s出發(fā)的路徑的一條弧出發(fā)的路徑的一條弧.2532172224 223111211s2453t054321t02211121 23s45113231 23012235搜索從搜索從 s 開始的最短開始的最短 s-t 途徑途徑如果路徑達(dá)到了如果路徑達(dá)到了 t, 那么發(fā)送流且更新剩余網(wǎng)絡(luò)那么發(fā)送流且更

7、新剩余網(wǎng)絡(luò).182334 12311121s2453t054321t02211121 23s45這是更新了的殘留容量這是更新了的殘留容量11321 23235192334 12311121s2453t054321t02211121 23s45搜索最短搜索最短 s-t 途徑途徑11321 232353 40123s1下一步下一步: 更新殘留容量更新殘留容量20234221111s2453t054321t02211121 2345這是更新了的殘留容量這是更新了的殘留容量2221 232353 41s121234221111s2453t054321t02211121 2345更新距離標(biāo)號和路徑更新距離標(biāo)號和路徑2221 232353 41s1234假設(shè)假設(shè) d(s) n-1, 那么沒有從那么沒有從s到到 t的路徑