標號法求最短路徑例題詳解.ppt_第1頁
標號法求最短路徑例題詳解.ppt_第2頁
標號法求最短路徑例題詳解.ppt_第3頁
標號法求最短路徑例題詳解.ppt_第4頁
標號法求最短路徑例題詳解.ppt_第5頁
已閱讀5頁，還剩7頁未讀， 繼續免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

最短路徑 帶權圖G 其中w E R e E w e 稱作e的權 e vi vj 記w e wij 若vi vj不相鄰 記wij 設L是G中的一條路徑 L的所有邊的權之和稱作L的權 記作w L u和v之間的最短路徑 u和v之間權最小的通路 例1L1 v0v1v3v5 w L1 10 L2 v0v1v4v5 w L2 12 L3 v0v2v4v5 w L3 11 1 標號法 E W Dijkstra 1959 設帶權圖G 其中 e E w e 0 設V v1 v2 vn 求v1到其余各頂點的最短路徑p標號 永久性標號 第r步獲得的v1到vi最短路徑的權t標號 臨時性標號 第r步獲得的v1經過p標號頂點到達vi的路徑的最小權 是v1到vi的最短路徑的權的上界第r步通過集Pr v v在第r步已獲得永久性標號 第r步未通過集Tr V Pr 2 標號法 續 3 標號法求最短路徑第一步 4 因為第一步v0只能夠到達v1和v2 所以v1和v2下面寫到達的權重 而v3 v5寫無窮大 標號法求最短路徑第二步 5 因為第一步得到的數字當中除了已經確定的0以外 1最小 所以到達v1的最短路徑確定了 為1 并且通過v0 因為通過v1到達v2需要3步 比4小 所以v2處寫3 同理 因為通過v1到達v3和v4的權重和小于正無窮 標號法求最短路徑第三步 6 因為第二步得到的數字當中3最小 v2最短為3 因為通過v2不能直接到達v3 所以v3下面還是8 通過v2到達v4需要4到達不了v5 7 可編輯 標號法求最短路徑第四步 8 標號法求最短路徑第五步 9 10 同理得到第五行 只是得到第五行以后所有都標紅了 也就是所有都結束了 最后加一行 把所有標紅的數字重新

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論