迪杰斯特拉算法總結.doc

《迪杰斯特拉算法總結.doc》由會員上傳分享，免費在線閱讀，更多相關內容在工程資料-天天文庫。

1、總結：最短路徑算法關鍵先把已知最短路徑頂點集(只有一個源點)和未知的頂點分開，然后依次把未知集合的頂點按照最短路徑(這里特別強調一下是源點到該頂點的路徑權重和，不僅僅是指它和父結點之間的權重，一開始就是在沒有這個問題弄清楚)加入到已知結點集中。在加入時可以記錄每個頂點的最短路徑，也可以在加入完畢后回溯找到每個頂點的最短路徑和權重。迪杰斯特拉算法用于求解一個有向圖（也可以是無向圖，無向圖是有向圖的一種特例）的一個點（稱之為原點）到其余各點（稱之為周邊點）的最短路徑問題。算法構思很是巧妙（我這么認為），簡直達到了“無心插柳柳成蔭”的境界。算法本身并不

2、是按照我們的思維習慣——求解從原點到第一個點的最短路徑，再到第二個點的最短路徑，直至最后求解完成到第n個點的最短路徑，而是求解從原點出發(fā)的各有向路徑的從小到大的排列（如果這個有向圖中有環(huán)1-2-3-1算法豈不是永無終結之日了？？！?。?，但是算法最終確實得到了從原點到圖中其余各點的最短路徑，可以說這是個副產品，對于算法的終結條件也應該以求得了原點到圖中其余各點的最短路徑為宜。清楚了算法的這種巧妙構思后，理解算法本身就不是難題了。算法把一個圖（G）中的點劃分成了若干部分：1）：原點（v）；2）：所有周邊點（C）；另外有一個輔助集合S，從v到S中的點的

3、最短路徑已經求得。S的最初狀態(tài)是空集。這樣就可以進一步劃分圖（G）：1）：原點（v）；2）：已求出v至其最短路徑的周邊點（S）；3）：尚未求出v至其最短路徑的周邊點（Other=C-S）；算法的主體思想：A、找到v——Other所有路徑中的的最短路徑vd=v——d（Other的一個元素）；B、找到v——S——Other所有路徑中的的最短路徑vi=v——i（Other的一個元素）；C、比較vd和vi如果vd<=vi則將d加入S且從Other中刪除，否則將i加入S且從Other中刪除。重復以上步驟直至Other為空集。我們求得的最短路徑是升序排列的，

4、那為什么下一條最短路徑就存在于v——用到了貪心的策略找最短的未拓展節(jié)點，加入已拓展部分然后再根據此節(jié)點，重新更新未拓展部分就是通過一個方法，找到起始位置到目標位置的最優(yōu)化路線Dijkstra算法是典型最短路算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低?！　ijkstra算法是很有代表性的最短路算法，在很多專業(yè)課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等?！　ijkstra一般的表述通

5、常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN,CLOSE表方式，Drew為了和下面要介紹的A*算法和D*算法表述一致，這里均采用OPEN,CLOSE表的方式?！　∑洳捎玫氖秦澬姆ǖ乃惴ú呗浴　〈蟾胚^程：　　創(chuàng)建兩個表，OPEN,CLOSE。　　OPEN表保存所有已生成而未考察的節(jié)點，CLOSED表中記錄已訪問過的節(jié)點?！　?．訪問路網中距離起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查?！　?．從OPEN表中找出距起始點最近的點，找出這個點的所有子節(jié)點，把這個點放到CLOSE表中。　　3．遍歷考察這個點的子節(jié)點。求出這

6、些子節(jié)點距起始點的距離值，放子節(jié)點到OPEN表中?！　?．重復第2和第3步,直到OPEN表為空，或找到目標點。