资源描述：
《论文资料：网路模式(network》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、精品文档免费阅读免费分享如需请下载！第九章網路模式(NetworkModels)本章內容：9.1最短路徑問題9.2最小展開樹問題9.3最大流量問題请下载！精品文档免费阅读免费分享如需请下载！■9.1最短路問題◆最短路徑問題係在一個網路中找尋節點1到每個其他節點間的最短路徑。◆若網路中所有的弧(arcs)為非負值，則以標籤法(Label)來找網路中一特定節點至所有其他節點之最短路徑。◆最短路徑問題中不限於求距離之極小化，其亦可解決時間或成本之極小化問題。標籤法：以一中括號〔〕為標籤，如下圖所示：從節點1至本節點之距離是20路徑上從節點
2、1到本節點的前一個節點為節點4请下载！精品文档免费阅读免费分享如需请下载！[20,4]節點標籤節點圖9.2節點標籤之例第一個數字表示從節點1到此節點的距離。第二數字從節點1到本節的路徑上，本節點的前一個節點。已找出從節點1至某節點的最短距離，這個節點稱為有一個永久的標籤(permanentlabel)，由節點1至某節點的最短距離的尚未找出來，這個節點就說有一個暫時的標節籤(tentativelabel)。一開始給節點1永久標籤[O,S]。O表示從節點1到它自己的距離是零，S表示節點1為起始節點。用一個箭頭指著某永久標籤,正研究這個永
3、久標籤。请下载！精品文档免费阅读免费分享如需请下载！例：哥曼公司有幾個建築計劃，下圖說明辦公室與6個工地的關係，兩個位置之間的距離，寫在弧上，哥曼要找出路徑，使公司到各工地之旅行距離最短。23456711531042517646道路長度(哩)哥曼的辦公室请下载！精品文档免费阅读免费分享如需请下载！圖9.1哥曼公司最短路徑問題網路圖解：開始時只有節點1為永久標籤23456711531042517646[0,S]请下载！精品文档免费阅读免费分享如需请下载！圖9.3哥曼最短路徑問題起始網路標籤考慮所有可由節點1直接到達的節點(節點2,3)
4、：節點2：節點1至節點2的直接距離為15里，所以節點2的暫時標籤為〔15,1〕。節點3：節點1到節點3的直接距離是10里。所以節點3的暫時標籤為〔10,1〕。23456711531042517646[0,S][15,1][10,1]请下载！精品文档免费阅读免费分享如需请下载！圖9.4哥曼網路之中，節點2及3有暫時標籤23456711531042517646[0,S][15,1][10,1]考慮所有暫時標籤的節點(節點2,3)，並找出在標籤中距離最小者為永久標籤；所以節點3是永久標籤，距離是10里。用一箭頭指著它，表示標籤法的下一步由
5、它開始。请下载！精品文档免费阅读免费分享如需请下载！圖9.5哥曼網路，節點３為永久標籤節點考慮所有可由節點3直接到達的節點：節點2：到節點3的最短距離是10里ð節點3到節點2的直接距離是10+3=13里，所以節點2的暫時標籤改為〔13,3〕。23456711531042517646[0,S][15,1][10,1][14,3][13,3]節點5：到節點３的最短距離是10里ð節點3到節點5的直接距離是10+4=14里，所以節點5的暫時標籤改為〔14,3〕。请下载！精品文档免费阅读免费分享如需请下载！圖9.6哥曼網路，節點2及5有新暫時
6、標籤[19,2]23456711531042517646[0,S][10,1][14,3][13,3][30,2]考慮所有暫時標籤的節點(節點2,5)，並找出其距離值最小者為永久標籤。所以節點2變成永久標籤，距離是13里。用一箭頭指著它，表示標籤法的下一步由它開始。请下载！精品文档免费阅读免费分享如需请下载！圖9.7哥曼網路，節點2有永久標籤，節點4及７有新暫時標籤考慮所有可由節點2直接到達的節點(節點4,7)：请下载！精品文档免费阅读免费分享如需请下载！節點4：到節點2的最短距離是13里ð節點2到節點4的直接距離是13+6=19里
7、，所以節點4的暫時標籤為[19,2]節點7：到節點2的最短距離是13里ð節點2到節點7的直接距離是13+17=30里，所以節點7的暫時標籤為[30,2]考慮所有可由節點3直接到達的節點(節點5)節點5：到節點3的最短距離是10里ð節點3到節點5的直接距離是10+4=14里，所以節點5的暫時標籤為[15,3]在所有暫時標籤節點(節點4,5,7)選最小者為永久標籤，所以標籤5變成永久標籤，用一個箭頭指著它，表示標籤法的下一步由它開始。因此節點4的暫時標籤需從[19,2]，改為[18,5]请下载！精品文档免费阅读免费分享如需请下载！234
8、56711531042517646[0,S][10,1][14,3][13,3][30,2][16,5][19,2][18,5]请下载！精品文档免费阅读免费分享如需请下载！圖9.8節點5有永久標籤，節點4，6有新暫時標籤 23456
