網(wǎng)路的最大流和最小截-資料下載頁(yè)
2025-05-13 06:10本頁(yè)面
【正文】 0 )( 1 0 , 0 )( 1 0 , 0 )發(fā)點(diǎn) 120發(fā)點(diǎn) 220收點(diǎn) 115收點(diǎn) 220( 5 , 0 )( , 1( 1 0 , 1 0 )555555( 1 0 , 1 0 )5虛發(fā)點(diǎn)虛收點(diǎn)st( 2 0 , 1 5 )( 2 0 , 1 5 )( 2 0 , 1 5 )( 1 5 , 1 5 )( 5 , 0 )10 最小費(fèi)用最大流 ? 雙權(quán)網(wǎng)路 ：每條弧不但有容量，還有單位流量的通過(guò)費(fèi)用 ? 兩種解法：一種基于最小費(fèi)用路徑算法；一種基于可行弧集的最大流算法 ? 基于最小費(fèi)用路徑算法 ：總是在當(dāng)前找到的最小費(fèi)用的路徑上增廣流；缺點(diǎn)是每次增廣后要改變弧的費(fèi)用，且出現(xiàn)負(fù)權(quán)值費(fèi)用的弧 ? 基于可行弧集的最大流算法 ：從 0 費(fèi)用弧集開(kāi)始應(yīng)用最大流算法，然后根據(jù)計(jì)算信息提高費(fèi)用的限界 P，使可行弧集增大，再應(yīng)用最大流算法，直至所有弧都進(jìn)入可行弧集。這種算法是一種主 對(duì)偶規(guī)劃的解法。使用這種方法的還有運(yùn)輸問(wèn)題、匹配問(wèn)題 11 以最短路為基礎(chǔ)匯總網(wǎng)路上的流 1324 5電路交換網(wǎng)1324 5傳輸網(wǎng)? 在電路網(wǎng)中每?jī)牲c(diǎn)之間都有中繼電路群需求，但并不是任兩點(diǎn)都有物理傳輸鏈路 ? 根據(jù)兩點(diǎn)間最短傳輸路徑將該兩點(diǎn)間的電路需求量加載到這條傳輸路徑上去：設(shè) a25=10 是節(jié)點(diǎn) 2 和 5 之間的電路需求，節(jié)點(diǎn) 2 和 5 之間的最短傳輸路徑為 2?1?3?5，則加載過(guò)程為 : T21=T21+10, T13=T13+10, T35=T35+10； Tij 是傳輸鏈路 i?j 上加載的電路數(shù)；當(dāng)所有點(diǎn)間電路都加載完則算法結(jié)束
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1