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

1、最大流問題的最短增廣途徑算法4114212331s2453t這是初始網(wǎng)絡(luò)，加上反向邊這是初始網(wǎng)絡(luò)，加上反向邊.4114212331s2453t這是初始網(wǎng)絡(luò)和初始?xì)埩艟W(wǎng)絡(luò)這是初始網(wǎng)絡(luò)和初始?xì)埩艟W(wǎng)絡(luò).4114212331s2453t結(jié)點(diǎn)標(biāo)號(hào)從此以后將是間隔標(biāo)號(hào)結(jié)點(diǎn)標(biāo)號(hào)從此以后將是間隔標(biāo)號(hào).054321t453s2d(j)是在是在G(f)中的中的j到到t的的最短的間隔的的最短的間隔0221114114212331s2453t弧弧 (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)入弧將表示成粗線.424241121331s2453t運(yùn)用可進(jìn)入弧從運(yùn)用可進(jìn)入弧從 s 開場(chǎng)進(jìn)展深度優(yōu)先搜索開場(chǎng)進(jìn)展深度優(yōu)先搜索.054321t453s2022111下一步下一步. 發(fā)送流并更新殘留容量發(fā)送流并更新殘留容量.21024 2241121331s2453t這里是更新后的殘留容量這里是更新后的殘留容量.054321t453s2022111假設(shè)需求，將在以后更新間隔標(biāo)號(hào)假設(shè)需求，將在以后更新間隔標(biāo)號(hào)24 2241121331s2453t054321t453s2022111運(yùn)用可進(jìn)入弧從運(yùn)用可進(jìn)入弧從 s 開場(chǎng)進(jìn)展深度優(yōu)先搜索開場(chǎng)進(jìn)展深度優(yōu)先搜索.下一

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

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

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

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

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