最大流問題的最短增廣路徑算法優(yōu)秀PPT

最大流問題的最短增廣路徑算法最短增廣路徑24114212331s2453t這是初始網(wǎng)絡(luò)，加上反向邊.最短增廣路徑34114212331s2453t這是初始網(wǎng)絡(luò)和初始?xì)埩艟W(wǎng)絡(luò).初始化距離44114212331s2453t結(jié)點(diǎn)標(biāo)號(hào)從此以后將是距離標(biāo)號(hào).054321t453s2d(j)是在G(f)中的j到t的的最短的距離022111可進(jìn)入弧的表示54114212331s2453t弧(i,j)是可進(jìn)入的，假設(shè)d(i)=d(j)+1.054321t453s2一條可進(jìn)入弧的s-t路徑是最短路徑.022111可進(jìn)入弧將表示成粗線.尋找最短s-t途徑6424241121331s2453t使用可進(jìn)入弧從s開始進(jìn)行深度優(yōu)先搜索.054321t453s2022111下一步.發(fā)送流并更新殘留容量.210更新殘留容量7242241121331s2453t這里是更新后的殘留容量.054321t453s2022111如果需要，將在以后更新距離標(biāo)號(hào)尋找最短s-t途徑8242241121331s2453t054321t453s2022111使用可進(jìn)入弧從s開始進(jìn)行深度優(yōu)先搜索.下一步.發(fā)送流并更新殘留容量.210更新剩余容量92224224111311s2453t054321t453s2022111這里是更新后的殘留容量.如果需要，將在以后更新距離標(biāo)號(hào)尋找最短s-t途徑102224224111311s2453t054321t453s2022111使用可進(jìn)入弧從s開始進(jìn)行深度優(yōu)先搜索.21如果沒有從i出發(fā)的可進(jìn)入弧，那么relabel(i)且沿著到i的路徑回溯.更新距離和路徑112224224111311s2453t054321t45s2022111使用可進(jìn)入弧從s開始進(jìn)行深度優(yōu)先搜索.21如果沒有從i出發(fā)的可進(jìn)入弧，那么relabel(i)且反向沿著從s出發(fā)的路徑的一條弧.23如果沒有從i出發(fā)的可進(jìn)入弧，那么relabel(i)且反向沿著從s出發(fā)的路徑的一條弧.可進(jìn)入弧將表示成粗線.如果路徑達(dá)到了t,那么發(fā)送流且更新剩余網(wǎng)絡(luò).這里是更新后的殘留容量.如果需要，將在以后更新距離標(biāo)號(hào)最大流問題的最短增廣路徑算法一條可進(jìn)入弧的s-t路徑是最短路徑.殘留網(wǎng)絡(luò)中找不到s-t途徑弧(i,j)是可進(jìn)入的，假設(shè)d(i)=d(j)+1.得到最大流時(shí)的殘留網(wǎng)絡(luò)如果需要，將在以后更新距離標(biāo)號(hào)d(j)是在G(f)中的j到t的的最短的距離發(fā)送流并更新殘留容量.如果沒有從i出發(fā)的可進(jìn)入弧，那么relabel(i)且反向沿著從s出發(fā)的路徑的一條弧.這是初始網(wǎng)絡(luò)，加上反向邊.更新距離和路徑122224224111311s2453t054321ts2022111使用可進(jìn)入弧從s開始進(jìn)行深度優(yōu)先搜索.21如果沒有從i出發(fā)的可進(jìn)入弧，那么relabel(i)且反向沿著從s出發(fā)的路徑的一條弧.233s45尋找最短s-t途徑132224224111311s2453t054321t2022111繼續(xù)從它離開的地方的路徑21如果路徑達(dá)到了t,那么發(fā)送流且更新剩余網(wǎng)絡(luò).233s02145更新殘留容量142224223111211s2453t054321t202211121233s45這是更新后的殘留容量.11搜索最短s-t途徑152224223111211s2453t054321t202211121233s45搜索從s開始的最短s-t途徑113231如果沒有從i出發(fā)的可進(jìn)入弧，那么relabel(i)且反向沿著從s出發(fā)的路徑的一條弧.搜索最短s-t途徑162224223111211s2453t054321t202211121233s45搜索從s開始的最短s-t途徑113231如果沒有從i出發(fā)的可進(jìn)入弧，那么relabel(i)且反向沿著從s出發(fā)的路徑的一條弧.2532搜索最短s-t途徑172224223111211s2453t054321t0221112123s4511323123012235搜索從s開始的最短s-t途徑如果路徑達(dá)到了t,那么發(fā)送流且更新剩余網(wǎng)絡(luò).更新殘留容量18233412311121s2453t054321t0221112123s45這是更新了的殘留容量1132123235這是初始網(wǎng)絡(luò)，加上反向邊.得到最大流時(shí)的殘留網(wǎng)絡(luò)使用可進(jìn)入弧從s開始進(jìn)行深度優(yōu)先搜索.如果沒有從i出發(fā)的可進(jìn)入弧，那么relabel(i)且反向沿著從s出發(fā)的路徑的一條弧.如果需要，將在以后更新距離標(biāo)號(hào)一條可進(jìn)入弧的s-t路徑是最短路徑.d(j)是在G(f)中的j到t的的最短的距離如果沒有從i出發(fā)的可進(jìn)入弧，那么relabel(i)且反向沿著從s出發(fā)的路徑的一條弧.假設(shè)d(s)>n-1,那么沒有從s到t的路徑d(j)是在G(f)中的j到t的的最短的距離使用可進(jìn)入弧從s開始進(jìn)行深度優(yōu)先搜索.搜索最短s-t途徑弧(i,j)是可進(jìn)入的，假設(shè)d(i)=d(j)+1.發(fā)送流并更新殘留容量.尋找最短s-t途徑得到最大流時(shí)的殘留網(wǎng)絡(luò)結(jié)點(diǎn)標(biāo)號(hào)從此以后將是距離標(biāo)號(hào).搜索最短s-t途徑19233412311121s2453t054321t0221112123s45搜索最短s-t途徑1132123235340123s1下一步:更新殘留容量更新殘留容量20234221111s2453t054321t022111212345這是更新了的殘留容量222123235341s1搜索最短s-t途徑21234221111s2453t054321t022111212345更新距離標(biāo)號(hào)和路徑222123235341s1234假設(shè)d(s)>n-1,那么沒有從s到t的路徑