dijkstra算法實現(xiàn)綜述

《dijkstra算法實現(xiàn)綜述》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、Dijkstra算法實現(xiàn)綜述摘要：Dijkstra算法是典型的最短路徑算法，用于計算一個結(jié)點到其他所有結(jié)點的最短路徑。Dijkstra的變形和應(yīng)用非常多,需要一定的時間和題量積累，通過改進獲得精度較高的結(jié)果。一、前言最短路徑問題是在給定的網(wǎng)絡(luò)圖中尋找出一條從起始點到目標點之間最短路徑。最短路算法不僅在GIS的交通路線導(dǎo)航、路徑分析領(lǐng)域應(yīng)用廣泛,在解決路徑搜索相關(guān)的應(yīng)用中也十分普遍,包括網(wǎng)絡(luò)路由算法、機器人探路、人工智能、游戲設(shè)計等等。?最短路徑是在很多的路徑中，找尋行經(jīng)距離最短、或者說所花費成本最少的路徑。由於交通運輸?shù)谋憷c普及，

2、所以兩地之間有發(fā)生運送或者資訊的傳遞下，最短路徑(ShortestPath)的問題隨時都可能會有需求產(chǎn)生。一般應(yīng)用的領(lǐng)域涵蓋很廣泛，如物流配送、貨運快遞郵務(wù)信件配送、警力巡邏、消防救災(zāi)救護、設(shè)施規(guī)劃、生產(chǎn)排程、電子電路、水管配置、行動通訊、及電腦網(wǎng)路等。二、技術(shù)說明：Dijkstra算法迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。Dijkstra經(jīng)典算法是由計算機科學家EdsgerDijkstra在文獻中提出的。它是一個圖的搜索算法，解決帶非負權(quán)重圖的單元最短路徑問題并產(chǎn)生一棵最短路徑樹。

3、該算法經(jīng)常使用在網(wǎng)絡(luò)路由和地理信息系統(tǒng)中。Dijkstra算法是典型的最短路徑算法，用于計算一個結(jié)點到其他所有結(jié)點的最短路徑。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。Dijkstra算法的基本思想是以源點為圓心，按最短路徑長度遞增的順序通過對路徑長度迭代得到從源點到其他各目標結(jié)點的最短路徑。迪杰斯特拉算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一

4、種是用OPEN,CLOSE表的方式，這里均采用永久和臨時標號的方式。注意該算法要求圖中不存在負權(quán)邊。其基本原理是：每次新擴展一個距離最短的點，更新與其相鄰的點的距離。當所有邊權(quán)都為正時，由于不會存在一個距離更短的沒擴展過的點，所以這個點的距離永遠不會再被改變，因而保證了算法的正確性。不過根據(jù)這個原理，用Dijkstra求最短路的圖不能有負權(quán)邊，因為擴展到負權(quán)邊的時候會產(chǎn)生更短的距離，有可能就破壞了已經(jīng)更新的點距離不會改變的性質(zhì)。具體如下：（1）算法分配給每個節(jié)點一個初步的距離值：設(shè)置初始節(jié)點為零和其他節(jié)點為無窮；（2）將當前訪問節(jié)點

5、設(shè)置為初始節(jié)點，其他的所有節(jié)點設(shè)置為未訪問節(jié)點，并創(chuàng)建一個未訪問節(jié)點集合；（3）針對當前節(jié)點，計算其與所有鄰接節(jié)點的距離。將計算出來的距離值與當前值進行比較，指定較小的一個。（4）當我們考慮完當前節(jié)點的所有鄰接節(jié)點，標記當前為已訪問，并將其從未訪問集合刪除。已訪問節(jié)點將永遠不會被訪問；（5）選擇為訪問過的標記最小試探距離的節(jié)點，并將其作為新的當前節(jié)點，然后回到步驟3；（6）如果終止節(jié)點已標記訪問或者最小試探性距離在未設(shè)置節(jié)點之間是無限的，該算法已完成?！∨e例來說，如果圖中的頂點表示城市，而邊上的權(quán)重表示著城市間開車行經(jīng)的距離。Dij

6、kstra算法可以用來找到兩個城市之間的最短路徑?！　ijkstra算法的輸入包含了一個有權(quán)重的有向圖G，以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑相連。我們以E所有邊的集合，而邊的權(quán)重則由權(quán)重函數(shù)w:E→[0,∞]定義。因此，w(u,v)就是從頂點u到頂點v的非負花費值(cost)。邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。已知有V中有頂點s及t，Dijkstra算法可以找到s到t的最

7、低花費路徑(i.e.最短路徑)。這個算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。算法描述　　這個算法是通過為每個頂點v保留目前為止所找到的從s到v的最短路徑來工作的。初始時，源點s的路徑長度值被賦為0（d[s]=0），同時把所有其他頂點的路徑長度設(shè)為無窮大，即表示我們不知道任何通向這些頂點的路徑（對于V中所有頂點v除s外d[v]=∞）。當算法結(jié)束時，d[v]中儲存的便是從s到v的最短路徑，或者如果路徑不存在的話是無窮大。Dijstra算法的基礎(chǔ)操作是邊的拓展：如果存在一條從u到v的邊，那么從s到u的最短路徑可以通

8、過將邊(u,v)添加到尾部來拓展一條從s到v的路徑。這條路徑的長度是d[u]+w(u,v)。如果這個值比目前已知的d[v]的值要小，我們可以用新值來替代當前d[v]中的值。拓展邊的操作一直執(zhí)行到所有的d[v]都代表從s到v最短路徑的花