dijkstra最短路演算法

❶ 綆璋堣開鍏嬫柉鐗規媺綆楁硶

涓鐩存兂瑕佸︾偣綆鍗曠殑綆楁硶錛屽彣鍙ㄤ簡濂戒箙錛屽紑濮嬪惂銆愯繖綃囨枃絝犵殑鍓嶈█鏃犻潪灝辨槸鎴戞兂璇寸偣搴熻瘽錛屽ぇ瀹跺彲浠ラ夋嫨鎬х殑榪囨護鍝堛傘

榪鏉版柉鐗規媺綆楁硶(Dijkstra)鏄鐢辮嵎鍏拌＄畻鏈虹戝﹀ 鐙勫厠鏂鐗規媺 浜1959 騫存彁鍑虹殑錛屽洜姝ゅ張鍙 鐙勫厠鏂鐗規媺綆楁硶 銆傛槸浠庝竴涓欏剁偣鍒板叾浣欏悇欏剁偣鐨 鏈鐭璺寰 綆楁硶錛岃В鍐崇殑鏄鏈夋潈鍥句腑鏈鐭璺寰勯棶棰樸傝開鏉版柉鐗規媺綆楁硶涓昏佺壒鐐規槸浠ヨ搗濮嬬偣涓轟腑蹇冨悜澶栧眰灞傛墿灞曪紝鐩村埌鎵╁睍鍒扮粓鐐逛負姝銆

鏁查粦鏉縹榪涘叆姝ｉ
榪鏉版柉鐗規媺綆楁硶鏄鐩鍓 OIER 浠鏈鐖辯敤鐨勬渶鐭璺綆楁硶錛屼笅闈㈣蹭竴涓嬭繖涓綆楁硶鐨勬濊礬銆愬浘涓戱紝璇峰ぇ瀹跺繊鑰愪竴涓嬨戱細

絎涓姝ワ紝鎴戜滑鍏堟妸a鍔犲叆闆嗗悎錛屾暟緇勫彉鎴愶紙s = {a}, dis[] = {0, 鈭,鈭,鈭,鈭,鈭,鈭,鈭瀩錛
絎浜屾ワ紝鎵懼埌鍜宎鏈榪戠殑鐐癸紝涓篵錛屾妸b鍔犲叆闆嗗悎錛屽苟紜瀹氫粬鐨勬渶鐭璺寰勩愯佹敞鎰忕澶存柟鍚戝搱銆戱紝鏁扮粍鍙樻垚錛坰 = {a, b}, dis[] ={0,2,鈭,鈭,鈭,鈭,鈭,鈭瀩錛
絎涓夋ワ紝鎵懼埌鍜宐鏈榪戠殑鐐癸紝涓篸錛屾妸d鍔犲叆闆嗗悎錛屽苟紜瀹氫粬鐨勬渶鐭璺寰勩愯佹敞鎰忕澶存柟鍚戙戱紝鏁扮粍鍙樻垚錛坰 = {a, b, d}, dis[] = {0,2,鈭,3,鈭,鈭,鈭,鈭瀩錛
絎鍥涙ワ紝鎵懼埌鍜宒鏈榪戠殑鐐癸紝涓篹錛屾妸e鍔犲叆闆嗗悎錛屽苟紜瀹氫粬鐨勬渶鐭璺寰勩愯佹敞鎰忕澶存柟鍚戙戱紝鏁扮粍鍙樻垚錛坰 = {a, b, d, e}, dis[] = {0,2,鈭,3,5,鈭,鈭,鈭瀩錛
絎浜旀ワ紝鎵懼埌鍜宔鏈榪戠殑鐐癸紝涓篺錛屾妸f鍔犲叆闆嗗悎錛屽苟紜瀹氫粬鐨勬渶鐭璺寰勩愯佹敞鎰忕澶存柟鍚戙戱紝鏁扮粍鍙樻垚錛坰 = {a, b, d, e, f}, dis[] = {0,2,鈭,3,5,9,鈭,鈭瀩錛
絎鍏姝ワ紝鎵懼埌鍜宖鏈榪戠殑鐐癸紝涓篻錛屾妸g鍔犲叆闆嗗悎錛屽苟紜瀹氫粬鐨勬渶鐭璺寰勩愯佹敞鎰忕澶存柟鍚戙戱紝鏁扮粍鍙樻垚錛坰 = {a, b, d, e, f, g}, dis[] = {0,2,鈭,3,5,9,12,鈭瀩錛
絎涓冩ワ紝鐩鍓嶅彧鍓╀笅c鍜宧浜嗭紝閭ｄ箞鎴戜滑鍏堣佹壘鍒拌窛紱婚泦鍚堣礬寰勬渶鐭鐨刢錛屾妸c鍔犲叆闆嗗悎錛屽苟紜瀹氫粬鐨勬渶鐭璺寰勶紝鏁扮粍鍙樻垚錛坰 = {a, b, c, d, e, f, g}, dis[]= {0,2,13,3,5,9,12,鈭瀩錛
絎鍏姝ワ紝鏈鍚庝竴姝ワ紝鎴戜滑鎵懼埌璺濈婚泦鍚堣礬寰勬渶鐭鐨刪錛屾妸h鍔犲叆闆嗗悎錛屽苟紜瀹氫粬鐨勬渶鐭璺寰勶紝鏁扮粍鍙樻垚錛坰 = {a, b, c, d, e, f, g, h}, dis[] = {0,2,13,3,5,9,12,18}錛
寰楀槥錛岃繖涓澶ц嚧鐨勬濊礬鏄榪欐牱鐨勶紝榪樻湁鍚庣畫鍝燂紝嬈茬煡鍚庝簨濡備綍錛岃風湅涓嬪洖璁茶В~

❷ 直觀理解：單源點最短路徑——Dijkstra演算法

  Dijkstra演算法是由荷蘭計算機科學家 Edsger Wybe Dijkstra於1959年提出的單源點最短路徑演算法（SSSP:Single Souce Shortest Path）。是一個解決加權圖（不含負權重的邊）中從一個頂點到其餘各個頂點最短路徑問題的演算法。Dijkstra演算法是一個集 貪心演算法 ， 廣度優先搜索（BFS） 和 動態規劃 於一身的最短路徑演算法。Dijkstra演算法的主要特點是從起源點開始，採用貪心演算法的策略，每次遍歷到始點距離最近且未訪問過的頂點的鄰接頂點，直到擴展到終點為止。
  Dijkstra演算法通過維護兩個集合： (已求出最短路徑的頂點)和 （未求出最短路徑的頂點），每次迭代地從 中移除路徑距離最小的點到集合 中，並通過這個新移入的點來更新 中各個頂點到源點的最短路徑，直到集合 為空。下面我們通過一個例子來簡單描述Dijkstra演算法的過程。
  假設我們有如下的圖，其中頂點A未此次演算法的起點：

  首先我們需要初始化兩個集合 和 ，以及 中每個頂點到源點的距離，若不直接於A相鄰，結果置為正無窮∞。

   Step 1： 從集合 中挑選出距離最小的點，這里會挑選出頂點F，集合 和 變更為： ， ，根據最新的 ，重新計算 中頂點到源點A的最短距離。

   Step 2:： 從集合 中挑選出距離最小的點，這里會挑選出頂點E，集合 和 變更為： ， ，根據最新的 ，重新計算 中頂點到源點A的最短距離。

   Step 3： 從集合 中挑選出距離最小的點，這里會挑選出頂點C，集合 和 變更為： ， ，根據最新的 ，重新計算 中頂點到源點A的最短距離。

   Step 4： 從集合 中挑選出距離最小的點，這里會挑選出頂點D，集合 和 變更為： ， ，根據最新的 ，重新計算 中頂點到源點A的最短距離。

   Step 5： 從集合 中挑選出距離最小的點，這里會挑選出頂點B，集合 和 變更為： ， ，根據最新的 ，重新計算 中頂點到源點A的最短距離。

   Step 6： 從集合 中挑選出距離最小的點，這里會挑選出頂點G，集合 和 變更為： ， ，由於集合 為空，演算法停止迭代，輸出結果。

  以上就是對Dijkstra演算法的計算過程的簡單描述。

❸ 綆榪癲ijkstra鏂規硶鐨勫熀鏈鎬濇兂

綆榪癲ijkstra鏂規硶鐨勫熀鏈鎬濇兂濡備笅錛

棣栧厛浠庤搗鐐筄寮濮嬶紝緇欐瘡涓鑺傜偣涓涓鏍囧彿錛屽垎涓篢鏍囧彿鍜孭鏍囧彿涓ょ被錛孴鏍囧彿鏄涓存椂鏍囧彿錛岃〃紺轟粠璧風偣O鍒拌ョ偣鐨勬渶鐭璺鏉冪殑涓婇檺;P鏍囧彿鏄鍥哄畾鏍囧彿錛岃〃紺轟粠璧風偣O鍒拌ョ偣鐨勬渶鐭璺鏉冦

鏍囧彿榪囩▼涓錛孴鏍囩偣涓鐩村湪鏀瑰彉錛孭鏍囧彿涓嶅啀鏀瑰彉錛屽嚒鏄娌℃湁鏍囦笂P鏍囧彿鐨勭偣錛岄兘鏍囦笂T鏍囧彿銆傜畻娉曠殑姣忎竴姝ユ妸鏌愪竴鐐圭殑T鏍囧彿璇ョ櫨騫翠負P鏍囧彿錛岀煡閬撴墍鏈夌殑T鏍囧彿閮借ユ敼鍙樹負P鏍囧彿銆傚嵆寰楀埌鑽夊嬬偣O鍒板叾浠栧悇鐐圭殑鏈鐭璺鏉冿紝鏍囧彿榪囩▼緇撴潫銆

涓銆丏ijkstra

Dijkstra鏄鍏稿瀷鏈鐭璺寰勭畻娉曪紝鐢ㄤ簬璁＄畻涓涓鑺傜偣鍒板叾浠栬妭鐐圭殑鏈鐭璺寰勩傝ョ畻娉曚嬌鐢ㄧ殑鏄璐蹇冪瓥鐣ワ細姣忔￠兘鎵懼嚭鍓╀綑欏剁偣涓涓庢簮鐐硅窛紱繪渶榪戠殑涓涓欏剁偣銆傜粰瀹氫竴甯︽潈鍥撅紝鍥句腑姣忔潯杈圭殑鏉冨兼槸闈炶礋鐨勶紝浠ｈ〃鐫涓ら《鐐逛箣闂寸殑璺濈匯傛寚瀹氬浘涓鐨勪竴欏剁偣涓烘簮鐐癸紝鎵懼嚭婧愮偣鍒板叾瀹冮《鐐圭殑鏈鐭璺寰勫拰鍏墮暱搴︾殑闂棰橈紝鍗蟲槸鍗曟簮鏈鐭璺寰勯棶棰樸

浜屻丏ijkstra鐨勫師鐞

鍒濆嬪寲鏃訛紝S鍙鍚鏈夋簮鑺傜偣銆備粠U涓閫夊彇涓涓璺濈籿鏈灝忕殑欏剁偣k鍔犲叆S涓錛堣ラ夊畾鐨勮窛紱誨氨鏄痸鍒発鐨勬渶鐭璺寰勯暱搴︼級銆備互k涓烘柊鑰冭檻鐨勪腑闂寸偣錛屼慨鏀筓涓鍚勯《鐐圭殑璺濈伙紱鑻ヤ粠婧愯妭鐐箆鍒伴《鐐箄鐨勮窛紱伙紙緇忚繃欏剁偣k錛夋瘮鍘熸潵璺濈伙紙涓嶇粡榪囬《鐐筴錛夌煭錛屽垯淇鏀歸《鐐箄鐨勮窛紱誨礆紝淇鏀瑰悗鐨勮窛紱誨兼槸欏剁偣k鐨勮窛紱誨姞涓妅鍒皍鐨勮窛紱匯

❹ 最短路徑演算法

Dijkstra演算法，A*演算法和D*演算法

Dijkstra演算法是典型最短路演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。

Dijkstra演算法是很有代表性的最短路演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。

Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 演算法和 D* 演算法表述一致，這里均採用OPEN,CLOSE表的方式。

大概過程：
創建兩個表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
1． 訪問路網中里起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查。
2． 從OPEN表中找出距起始點最近的點，找出這個點的所有子節點，把這個點放到CLOSE表中。
3． 遍歷考察這個點的子節點。求出這些子節點距起始點的距離值，放子節點到OPEN表中。
4． 重復2，3，步。直到OPEN表為空，或找到目標點。

提高Dijkstra搜索速度的方法很多，常用的有數據結構採用Binary heap的方法，和用Dijkstra從起始點和終點同時搜索的方法。

A*（A-Star)演算法是一種啟發式演算法，是靜態路網中求解最短路最有效的方法。

公式表示為： f(n)=g(n)+h(n),
其中f(n) 是節點n從初始點到目標點的估價函數，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n)是從n到目標節點最佳路徑的估計代價。

保證找到最短路徑（最優解的）條件，關鍵在於估價函數h(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。
如果 估價值>實際值, 搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。
估價值與實際值越接近，估價函數取得就越好。
例如對於幾何路網來說，可以取兩節點間歐幾理德距離（直線距離）做為估價值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優於Dijstra演算法的毫無無方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索過程：
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,->算X的估價值->
While(OPEN!=NULL)
{
從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
else
{
if(X in OPEN) 比較兩個X的估價值f //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於OPEN表的估價值 )
更新OPEN表中的估價值; //取最小路徑的估價值
if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於CLOSE表的估價值 )
更新CLOSE表中的估價值; 把X節點放入OPEN //取最小路徑的估價值
if(X not in both)
求X的估價值;
並將X插入OPEN表中; //還沒有排序
}
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
}

A*演算法和Dijistra演算法的區別在於有無估價值，Dijistra演算法相當於A*演算法中估價值為0的情況。

動態路網，最短路演算法 D*A* 在靜態路網中非常有效（very efficient for static worlds），但不適於在動態路網，環境如權重等不斷變化的動態環境下。

D*是動態A*（D-Star,Dynamic A*） 卡內及梅隆機器人中心的Stentz在1994和1995年兩篇文章提出，主要用於機器人探路。是火星探測器採用的尋路演算法。

主要方法：
1.先用Dijstra演算法從目標節點G向起始節點搜索。儲存路網中目標點到各個節點的最短路和該位置到目標點的實際值h,k（k為所有變化h之中最小的值,當前為k=h。每個節點包含上一節點到目標點的最短路信息1(2),2(5),5(4)，4（7）。則1到4的最短路為1-2-5-4。
原OPEN和CLOSE中節點信息保存。
2.機器人沿最短路開始移動，在移動的下一節點沒有變化時，無需計算，利用上一步Dijstra計算出的最短路信息從出發點向後追述即可，當在Y點探測到下一節點X狀態發生改變，如堵塞。機器人首先調整自己在當前位置Y到目標點G的實際值h(Y)，h(Y)=X到Y的新權值c(X,Y)+X的原實際值h(X).X為下一節點(到目標點方向Y->X->G），Y是當前點。k值取h值變化前後的最小。
3.用A*或其它演算法計算，這里假設用A*演算法,遍歷Y的子節點，點放入CLOSE,調整Y的子節點a的h值，h(a)=h(Y)+Y到子節點a的權重C(Y,a),比較a點是否存在於OPEN和CLOSE中，方法如下：
while()
{
從OPEN表中取k值最小的節點Y;
遍歷Y的子節點a,計算a的h值 h(a)=h(Y)+Y到子節點a的權重C(Y,a)
{
if(a in OPEN) 比較兩個a的h值
if( a的h值小於OPEN表a的h值 )
{ 更新OPEN表中a的h值;k值取最小的h值
有未受影響的最短路經存在
break;
}
if(a in CLOSE) 比較兩個a的h值 //注意是同一個節點的兩個不同路徑的估價值
if( a的h值小於CLOSE表的h值 )
{
更新CLOSE表中a的h值; k值取最小的h值;將a節點放入OPEN表
有未受影響的最短路經存在
break;
}
if(a not in both)
將a插入OPEN表中; //還沒有排序
}
放Y到CLOSE表；
OPEN表比較k值大小進行排序；
}
機器人利用第一步Dijstra計算出的最短路信息從a點到目標點的最短路經進行。

D*演算法在動態環境中尋路非常有效，向目標點移動中，只檢查最短路徑上下一節點或臨近節點的變化情況，如機器人尋路等情況。對於距離遠的最短路徑上發生的變化，則感覺不太適用。

❺ 已知帶權有向圖如圖7-29所示,請利用Dijkstra演算法從頂點V4出發到其餘頂點的最短路

初始化d[i]為無窮大，由於從v4開始，所以將d4=0，標記v4已選擇。
下面開始Dijkstra演算法：
和v4相連的且未標記的點有v2和v6，這樣更新d2=20，d6=15，選擇未標記所有點中最小的d6=15，標記v6已選擇，這樣我們算出了v4->v6最短距離d6=15；
從v6開始，和v6相連的且未標記的是v2，此時算d6+6=21>20,所以不更新d2，選擇未標記所有點中最小的d2=20，標記v2已選擇，這樣算出了v4->v2最短距離d2=20；
從v2開始，和v2相連的且未標記的有v1和v5，d1=d2+10=30,d5=d2+30=50，選擇未標記所有點中最小的d1=30，標記v1已選擇，這樣我們算出了v4->v1最短距離d1=30；
從v1開始，和v1相連的且未標記的有v3，d3=d1+15=45，選擇剩下沒被選的所有點的最小的d3=45(d5=50)，標記v3已選擇，這樣我們算出了v4->v3最短距離d3=45
從v3開始，沒有出去的路徑，不更新距離，選擇剩下沒被選的所有點的最小的d5=50，標記v5已選擇，這樣我們算出了v4->v5最短距離d5=50.
此時所有的點都被訪問，結束。
註：上面的標記點已選擇注意下，在演算法的實現中用的是將所有的點放入隊列中，一旦一個點被選擇就是說求出了最短距離，就從此隊列刪除該點，一直到此隊列為空，結束演算法，我寫標記只是為了方便理解。
希望能幫你清晰了解Dijkstra演算法，圖論中很重要的演算法之一。

❻ dijkstra演算法是什麼

Dijkstra演算法是由荷蘭計算機科學家狄克斯特拉（Dijkstra）於1959年提出的，因此又叫狄克斯特拉演算法。是從一個頂點到其餘各頂點的最短路徑演算法，解決的是有向圖中最短路徑問題。

其基本原理是：每次新擴展一個距離最短的點，更新與其相鄰的點的距離。當所有邊權都為正時，由於不會存在一個距離更短的沒擴展過的點，所以這個點的距離永遠不會再被改變，因而保證了演算法的正確性。

不過根據這個原理，用Dijkstra求最短路的圖不能有負權邊，因為擴展到負權邊的時候會產生更短的距離，有可能就破壞了已經更新的點距離不會改變的性質。

舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離。Dijkstra演算法可以用來找到兩個城市之間的最短路徑。

Dijkstra演算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。（u,v)表示從頂點u到v有路徑相連。我們以E所有邊的集合，而邊的權重則由權重函數w: E→[0,∞］定義。

因此，w(u,v)就是從頂點u到頂點v的非負花費值（cost)。邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。

已知有V中有頂點s及t，Dijkstra演算法可以找到s到t的最低花費路徑（i.e.最短路徑）。這個演算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。