資源描述:
《迪杰斯特拉算法總結(jié).doc》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。
1、總結(jié):最短路徑算法關(guān)鍵先把已知最短路徑頂點(diǎn)集(只有一個(gè)源點(diǎn))和未知的頂點(diǎn)分開(kāi),然后依次把未知集合的頂點(diǎn)按照最短路徑(這里特別強(qiáng)調(diào)一下是源點(diǎn)到該頂點(diǎn)的路徑權(quán)重和,不僅僅是指它和父結(jié)點(diǎn)之間的權(quán)重,一開(kāi)始就是在沒(méi)有這個(gè)問(wèn)題弄清楚)加入到已知結(jié)點(diǎn)集中。在加入時(shí)可以記錄每個(gè)頂點(diǎn)的最短路徑,也可以在加入完畢后回溯找到每個(gè)頂點(diǎn)的最短路徑和權(quán)重。迪杰斯特拉算法用于求解一個(gè)有向圖(也可以是無(wú)向圖,無(wú)向圖是有向圖的一種特例)的一個(gè)點(diǎn)(稱(chēng)之為原點(diǎn))到其余各點(diǎn)(稱(chēng)之為周邊點(diǎn))的最短路徑問(wèn)題。算法構(gòu)思很是巧妙(我這么認(rèn)為),簡(jiǎn)直達(dá)到了“無(wú)心插柳柳成蔭”的境界。算法本身并不
2、是按照我們的思維習(xí)慣——求解從原點(diǎn)到第一個(gè)點(diǎn)的最短路徑,再到第二個(gè)點(diǎn)的最短路徑,直至最后求解完成到第n個(gè)點(diǎn)的最短路徑,而是求解從原點(diǎn)出發(fā)的各有向路徑的從小到大的排列(如果這個(gè)有向圖中有環(huán)1-2-3-1算法豈不是永無(wú)終結(jié)之日了??!?。?,但是算法最終確實(shí)得到了從原點(diǎn)到圖中其余各點(diǎn)的最短路徑,可以說(shuō)這是個(gè)副產(chǎn)品,對(duì)于算法的終結(jié)條件也應(yīng)該以求得了原點(diǎn)到圖中其余各點(diǎn)的最短路徑為宜。清楚了算法的這種巧妙構(gòu)思后,理解算法本身就不是難題了。算法把一個(gè)圖(G)中的點(diǎn)劃分成了若干部分:1):原點(diǎn)(v);2):所有周邊點(diǎn)(C);另外有一個(gè)輔助集合S,從v到S中的點(diǎn)的
3、最短路徑已經(jīng)求得。S的最初狀態(tài)是空集。這樣就可以進(jìn)一步劃分圖(G):1):原點(diǎn)(v);2):已求出v至其最短路徑的周邊點(diǎn)(S);3):尚未求出v至其最短路徑的周邊點(diǎn)(Other=C-S);算法的主體思想:A、找到v——Other所有路徑中的的最短路徑vd=v——d(Other的一個(gè)元素);B、找到v——S——Other所有路徑中的的最短路徑vi=v——i(Other的一個(gè)元素);C、比較vd和vi如果vd<=vi則將d加入S且從Other中刪除,否則將i加入S且從Other中刪除。重復(fù)以上步驟直至Other為空集。我們求得的最短路徑是升序排列的,
4、那為什么下一條最短路徑就存在于v——用到了貪心的策略找最短的未拓展節(jié)點(diǎn),加入已拓展部分然后再根據(jù)此節(jié)點(diǎn),重新更新未拓展部分就是通過(guò)一個(gè)方法,找到起始位置到目標(biāo)位置的最優(yōu)化路線Dijkstra算法是典型最短路算法,用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展,直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解,但由于它遍歷計(jì)算的節(jié)點(diǎn)很多,所以效率低?! ijkstra算法是很有代表性的最短路算法,在很多專(zhuān)業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹,如數(shù)據(jù)結(jié)構(gòu),圖論,運(yùn)籌學(xué)等等?! ijkstra一般的表述通
5、常有兩種方式,一種用永久和臨時(shí)標(biāo)號(hào)方式,一種是用OPEN,CLOSE表方式,Drew為了和下面要介紹的A*算法和D*算法表述一致,這里均采用OPEN,CLOSE表的方式。 其采用的是貪心法的算法策略 大概過(guò)程: 創(chuàng)建兩個(gè)表,OPEN,CLOSE?! PEN表保存所有已生成而未考察的節(jié)點(diǎn),CLOSED表中記錄已訪問(wèn)過(guò)的節(jié)點(diǎn)?! ?.訪問(wèn)路網(wǎng)中距離起始點(diǎn)最近且沒(méi)有被檢查過(guò)的點(diǎn),把這個(gè)點(diǎn)放入OPEN組中等待檢查。 2.從OPEN表中找出距起始點(diǎn)最近的點(diǎn),找出這個(gè)點(diǎn)的所有子節(jié)點(diǎn),把這個(gè)點(diǎn)放到CLOSE表中?! ?.遍歷考察這個(gè)點(diǎn)的子節(jié)點(diǎn)。求出這
6、些子節(jié)點(diǎn)距起始點(diǎn)的距離值,放子節(jié)點(diǎn)到OPEN表中?! ?.重復(fù)第2和第3步,直到OPEN表為空,或找到目標(biāo)點(diǎn)。