迪杰斯特拉算法總結(jié).doc

迪杰斯特拉算法總結(jié).doc

ID:55170577

大?。?3.00 KB

頁數(shù):4頁

時間:2020-04-30

迪杰斯特拉算法總結(jié).doc_第1頁
迪杰斯特拉算法總結(jié).doc_第2頁
迪杰斯特拉算法總結(jié).doc_第3頁
迪杰斯特拉算法總結(jié).doc_第4頁
資源描述:

《迪杰斯特拉算法總結(jié).doc》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在工程資料-天天文庫

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

2、是按照我們的思維習(xí)慣——求解從原點到第一個點的最短路徑,再到第二個點的最短路徑,直至最后求解完成到第n個點的最短路徑,而是求解從原點出發(fā)的各有向路徑的從小到大的排列(如果這個有向圖中有環(huán)1-2-3-1算法豈不是永無終結(jié)之日了???。。撬惴ㄗ罱K確實得到了從原點到圖中其余各點的最短路徑,可以說這是個副產(chǎn)品,對于算法的終結(jié)條件也應(yīng)該以求得了原點到圖中其余各點的最短路徑為宜。清楚了算法的這種巧妙構(gòu)思后,理解算法本身就不是難題了。算法把一個圖(G)中的點劃分成了若干部分:1):原點(v);2):所有周邊點(C);另外有一個輔助集合S,從v到S中的點的

3、最短路徑已經(jīng)求得。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中刪除。重復(fù)以上步驟直至Other為空集。我們求得的最短路徑是升序排列的,

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

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

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

當前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細閱讀文檔內(nèi)容,確認文檔內(nèi)容符合您的需求后進行下載,若出現(xiàn)內(nèi)容與標題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。