最小樹最短路與最大流問題

《最小樹最短路與最大流問題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、最小樹、最短路與最大流問題最小樹與最短路問題的運(yùn)算程序是NetworkModeling（網(wǎng)絡(luò)模型），最小部分樹選擇MinimalSpanningTree，最短路選擇ShortestPathProblem，最大流問題選擇MaximalFlowProblem。1、如圖4-1所示，（1）求解最小部分樹問題，（2）分別求v1到v7和v2到v6的最短路及最短路長。（1）進(jìn)入圖4-2所示界面，選擇MinimalSpanningTree，，輸入節(jié)點(diǎn)數(shù)7。對照圖4-1輸入表4-1所示的數(shù)據(jù)。兩點(diǎn)間的權(quán)數(shù)只輸入一次（上三角）。圖4-1圖4-2表4-1點(diǎn)擊

2、菜單欄SolveandAnalyze，輸出表4-2最小樹結(jié)果，最小樹長為15。點(diǎn)擊菜單欄Results→GraphicSolution,，顯示最小部分樹形，見圖4-3。表4-2圖4-3（2）進(jìn)入圖4-2所示界面，選擇ShortestPathProblem，如果是有向圖就按弧的方向輸數(shù)據(jù)，本例是無向圖，每一條邊必須輸入兩次，無向邊變?yōu)閮蓷l方向相反的弧，見表4-3。點(diǎn)擊SolveandAnalyze后系統(tǒng)提示用戶選擇圖的起點(diǎn)和終點(diǎn)，系統(tǒng)默認(rèn)從第一個點(diǎn)到最后一個點(diǎn)，用戶選擇后系統(tǒng)不僅輸出v1到v7路徑和路長，還顯示了v1到各點(diǎn)的最短路長12，

3、見表4-4。點(diǎn)擊Result→GraphicSolution，顯示v1到各點(diǎn)的最短路線圖4-4。同理，選擇v2到v6得到最短路長為6，路徑為v2→v3→v6。表4-3表4-4圖4-41、用WinQSB軟件求解例7.15。進(jìn)入圖4-2所示界面，選擇MaximalFlowProblem。輸入節(jié)點(diǎn)數(shù)6，輸入表4-5所示的數(shù)據(jù)，輸入弧容量即可。表4-5點(diǎn)擊SolveandAnalyze后系統(tǒng)提示用戶選擇圖的起點(diǎn)和終點(diǎn)，系統(tǒng)默認(rèn)從第一個點(diǎn)到最后一個點(diǎn)，用戶選擇后系統(tǒng)不僅輸出v0到v5路徑和流量，還顯示了最大流量18，見表4-6。點(diǎn)擊Result→

4、GraphicSolution，顯示各點(diǎn)的流量圖4-5。表4-6圖4-5