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

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

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

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

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