網(wǎng)路的最大流和最小截-文庫吧
2025-04-23 06:10 本頁面
【正文】 到最大流 ? 增廣鏈中與 s 到 t 方向一致的弧稱為 前向弧 ，反之 后向弧 ? 增廣過程：前向弧 f?ij=fij +q , 后向弧 f?ij=fij ?q ? 增廣后仍是可行流 s t5432( 3,0) ( 5,3)( 1,1)( 5,1) ( 1,1)qs2= 4 q5t= 2q45= 3q43= 1q32= 1增廣量 q = m i n qij= m i n ( 4,1,1,3,2) = 1s t5432( 3,1) ( 5,4)( 1,0)( 5,2) ( 1,0)??? ??后向弧前向弧ijijijijffcq4 最大流最小截的標(biāo)號法步驟 第一步：標(biāo)號過程，找一條增廣鏈 給源點(diǎn) s 標(biāo)號 [s+,q(s)=?]，表示從 s 點(diǎn)有無限流出潛力 找出與已標(biāo)號節(jié)點(diǎn) i 相鄰的所有未標(biāo)號節(jié)點(diǎn) j，若 (1) (i, j)是前向弧且飽和，則節(jié)點(diǎn) j 不標(biāo)號； (2) (i, j)是前向弧且未飽和，則節(jié)點(diǎn) j 標(biāo)號為 [i+,q(j)]，表示從節(jié)點(diǎn) i 正向 流出，可增廣 q(j)=min[q(i), cij?fij] ； (3) (j, i)是后向弧，若 fji=0，則節(jié)點(diǎn) j 不標(biāo)號； (4) (j, i)是后向弧，若 fji0，則節(jié)點(diǎn) j 標(biāo)號為 [i?,q(j)]，表示從節(jié)點(diǎn) j 流向 i， 可增廣 q(j)=min[q(i), fji] ； 重復(fù)步驟 2，可能出現(xiàn)兩種情況： (1) 節(jié)點(diǎn) t 尚未標(biāo)號，但無法繼續(xù)標(biāo)記，說明網(wǎng)路中已不存在增廣鏈，當(dāng)前流 v(f) 就是最大流；所有獲標(biāo)號的節(jié)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1