下載本文檔
版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、精選優(yōu)質文檔-傾情為你奉上最短路徑之Dijkstra算法詳細講解 最短路徑算法在日常生活中,我們如果需要常常往返A地區(qū)和B地區(qū)之間,我們最希望知道的可能是從A地區(qū)到B地區(qū)間的眾多路徑中,那一條路徑的路途最短。最短路徑問題是圖論研究中的一個經典算法問題, 旨在尋找圖(由結點和路徑組成的)中兩結點之間的最短路徑。 算法具體的形式包括:()確定起點的最短路徑問題:即已知起始結點,求最短路徑的問題。 ()確定終點的最短路徑問題:與確定起點的問題相反,該問題是已知終結結點,求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同,在有向圖中該問題等同于把所有路徑方向
2、反轉的確定起點的問題。 ()確定起點終點的最短路徑問題:即已知起點和終點,求兩結點之間的最短路徑。 ()全局最短路徑問題:求圖中所有的最短路徑。用于解決最短路徑問題的算法被稱做“最短路徑算法”, 有時被簡稱作“路徑算法”。 最常用的路徑算法有:Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。本文主要研究Dijkstra算法的單源算法。 Dijkstra算法2.1 Dijkstra算法Dijkstra算法是典型最短路算法,用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展,直到
3、擴展到終點為止。Dijkstra算法能得出最短路徑的最優(yōu)解,但由于它遍歷計算的節(jié)點很多,所以效率低。Dijkstra算法是很有代表性的最短路算法,在很多專業(yè)課程中都作為基本內容有詳細的介紹,如數據結構,圖論,運籌學等等。2.2 Dijkstra算法思想Dijkstra算法思想為:設G=(V,E)是一個帶權有向圖,把圖中頂點集合V分成兩組,第一組為已求出最短路徑的頂點集合(用S表示,初始時S中只有一個源點,以后每求得一條最短路徑 , 就將 加入到集合S中,直到全部頂點都加入到S中,算法就結束了),第二組為其余未確定最短路徑的頂點集合(用U表示),按最短路徑長度的遞增次序依次把第二組的
4、頂點加入S中。在加入的過程中,總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外,每個頂點對應一個距離,S中的頂點的距離就是從v到此頂點的最短路徑長度,U中的頂點的距離,是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。2.3 Dijkstra算法具體步驟(1)初始時,S只包含源點,即S,v的距離為0。U包含除v外的其他頂點,U中頂點u距離為邊上的權(若v與u有邊)或 )(若u不是v的出邊鄰接點)。(2)從U中選取一個距離v最小的頂點k,把k,加入S中(該選定的距離就是v到k的最短路徑長度)。(3)以k為新考慮的中間點,修改U中各頂點的距離;若從源點v到頂點u(u U)的距離(經過頂點k)比原來距離(不經過頂點k)短,則修改頂點u的距離值,修改后的距離值的頂點k的距離加上邊上的權。(4)重復步驟(2)和(3)直到所有頂點都包含在S中。2.4 Dijkstra算法舉例說明如下圖,設A為源點,求A到其他各頂點(B、C、D、E、F)的最短路徑。線上所標注為相鄰線段之間的距離,即權值。(注:此圖為隨意所畫,其相鄰頂點間的距離與圖中的目視長度不能一一對等)圖一:Dijkstra無向圖 534
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 低成本教育材料銷售行業(yè)營銷策略方案
- 健身器材銷售與租賃行業(yè)相關項目現狀分析及對策
- 獨立音樂人行業(yè)市場發(fā)展趨勢及投資咨詢報告
- 2023年深圳市光明區(qū)人民醫(yī)院選聘專業(yè)技術崗位工作人員筆試真題
- 2023年昆明市盤龍區(qū)金辰街道辦事處社區(qū)服務中心崗位筆試真題
- 2023年達州市消防員招錄工作辦公室社會招錄政府專職消防員筆試真題
- 2024年天津客運駕駛從業(yè)資格證模擬考試題及答案
- 2024年延邊道路旅客運輸從業(yè)資格考試
- 2024年宣城小型客運從業(yè)資格證考試
- 海洋能開發(fā)行業(yè)的消費市場分析
- 2 我向國旗敬個禮 教學設計-2024-2025學年道德與法治一年級上冊統(tǒng)編版
- 2024年老年人能力評估師(技師)職業(yè)資格鑒定考試題庫(含答案)
- 2024年新華師大版數學七年級上冊全冊課件(新版教材)
- 2.1 認識自己(教學課件) -2024-2025學年七年級道德與法治上冊 (統(tǒng)編版2024)
- 學校重點部位保安人員巡邏制度
- 工商局規(guī)定格式2024公司股權轉讓合同樣本
- 【微專題】2014-2024高考語文文言文挖空訓練( I 卷、II 卷、甲卷、乙卷)教師版
- 2023年國家文物進出境審核海南管理處招聘事業(yè)編制工作人員考試真題
- 普惠性民辦幼兒園申報表
- 《荷花淀》教學課件
- HG∕T 4528-2013 牙膏用重質碳酸鈣
評論
0/150
提交評論