迪克斯特拉演算法的實驗結論和感悟

① Dijkstra演算法

Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。注意該演算法要求圖中不存在負權邊。

設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以後每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點都加入到S中，演算法就結束了），第二組為其餘未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大於從源點v到U中任何頂點的最短路徑長度含侍仿。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。

（1）初始時，S只包含起點D；U包含除D外的其他頂點，且U中頂點的距離為「起點D到該頂點的距離」（例如，U中頂點A的距離為[D,A]的長度，然後D和A不相鄰，則談棗A的距離為∞）
（2）從U中選出「距離最短的頂點K」，並將頂點K加入到S中；同時，從U中移除頂點K
（3）更新U中各個頂點到起點D的距離。之所以更新U中頂點的距離，是由於上一步談纖中確定了K是求出最短路徑的頂點，從而可以利用K來更新其他頂點到起點D的距離（例如，[D,A]的距離可能大於[D,K]+[K,A]的距離）
（4）重復步驟（2）和（3），直到遍歷完所有頂點

https://blog.csdn.net/yalishadaa/article/details/55827681

② 最短路徑演算法（Dijkstra）

Dijkstra（ 迪科斯特拉 ）演算法是用來解決核激唯單源最短路徑的演算法，要求路徑權值非負數。該演算法利用了深度優先搜索和貪心的演算法。

下面是一個有權圖，求從A到各個節點的最短路徑。

第1步：從A點出發，判斷每個點到A點的路徑（如果該點不能直連A點則距離值為無窮大，如果該點能和A直連則是當前的權值），計算完之後把A點上色，結果如下圖:

第2步：從除A點之外的點查找到距離A點最近的點C，從C點出發查找其鄰近的節點（除去已上色的點），並重新計算C點的鄰近點距離A點的值，如圖中B點，若新值（C點到A點的值+C點到該點的路徑）小於原值，則將值更新為5，同理更新D、E點。同時將C標鉛陵記為已經處理過，如圖所示塗色。

第3步：從上色的節點中查找距離A最近的B點，重復第3步操作。

第4步： 重復第3步，改培2步，直到所有的節點都上色。

最後就算出了從A點到所有點的最短距離。

leetcode 743題

③ 深入理解 Dijkstra 演算法實現原理

（嗯，第一段是抄的，由於本人演算法的基礎比較薄弱，我會盡量用通俗易懂的高念語言來讓大家理解本文）

參考博客: 數據結構--Dijkstra演算法最清楚的講解

大概就是這樣一個有權圖，液燃 Dijkstra 演算法可以計算 任意節點 到 其他節點 的最短路徑

2.執行上述 4、5兩步驟，找出U集合中路徑最短的節點D 加入S集合，並根據條件 if ( 'D 到 B,C,E 的距離' + 'AD 距離' < 'A 到 B,C,E 的距離' ) 來更新U集合

3.這時候 A->B, A->C 都為3，沒關系戚埋困。其實這時候他倆都是最短距離，如果從演算法邏輯來講的話，會先取到B點。而這個時候 if 條件變成了 if ( 'B 到 C,E 的距離' + 'AB 距離' < 'A 到 C,E 的距離' ) ， 如圖所示這時候 A->B 距離 其實為 A->D->B

④ 簡談迪克斯特拉演算法

一直想要學點簡單的演算法，叨叨了好久，開始吧【這篇文章的前言無非就是我想說點廢話，大家可以選擇性的過濾哈。】

迪傑斯特拉演算法(Dijkstra)是由荷蘭計算機科學家 狄克斯特拉 於1959 年提出的，因此又叫 狄克斯特拉演算法 。是從一個頂點到其餘各頂點的 最短路徑 演算法，解決的是有權圖中最短路徑問題。迪傑斯特拉演算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

敲黑板~進入正題
迪傑斯特拉演算法是目前 OIER 們最愛用的最短路演算法，下面講一下這個演算法的思路【圖丑，請大家忍耐一下】：

第一步，我們先把a加入集合，數組變成（s = {a}, dis[] = {0, ∞,∞,∞,∞,∞,∞,∞}）
第二步，找到和a最近的點，為b，把b加入集合，並確定他的最短路徑【要注意箭頭方向哈仿殲塌】，數組變成（s = {a, b}, dis[] ={0,2,∞,∞,∞,∞,∞,∞}）
第三步，找到和b最近的點，為d，把d加入集合，並確定他的最短路徑【要注意箭頭方向】，數組變成（s = {a, b, d}, dis[] = {0,2,∞,3,∞,∞,∞,∞}）
第四步，找到和d最近的點，為e，把e加入集合，並確定他的最短路徑【要注意箭頭方向】，數組變成（s = {a, b, d, e}, dis[] = {0,2,∞,3,5,∞,∞,∞改纖}）
第五步，找到和e最近的點，為f，把f加入集合，並確定他的最短路徑【要注意箭頭方向】，數組變成（s = {a, b, d, e, f}, dis[] = {0,2,∞,3,5,9,∞,∞}）
第六步，找到和f最近的點，為g，把g加入集合，並確定他的最短路徑【要注意箭頭方向】，數組變成（s = {a, b, d, e, f, g}, dis[] = {0,2,∞,3,5,9,12,∞}）
第七步，目前只剩下c和h了，那麼我們先要找到距離集合路徑最短的c，把c加備圓入集合，並確定他的最短路徑，數組變成（s = {a, b, c, d, e, f, g}, dis[]= {0,2,13,3,5,9,12,∞}）
第八步，最後一步，我們找到距離集合路徑最短的h，把h加入集合，並確定他的最短路徑，數組變成（s = {a, b, c, d, e, f, g, h}, dis[] = {0,2,13,3,5,9,12,18}）
得嘞，這個大致的思路是這樣的，還有後續喲，欲知後事如何，請看下回講解~

⑤ 最短路徑 | 深入淺出Dijkstra演算法（一）

上次我們介紹了神奇的只有 五行的 Floyd-Warshall 最短路演算法 ，它可以方便的求得 任意兩點的最短路徑， 這稱為 「多源最短路」。

這次來介紹 指定一個點（源點）到其餘各個頂點的最短路徑， 也叫做 「單源最短路徑」。 例如求下圖中的 1 號頂點到 2、3、4、5、6 號頂點的最短路徑。

與 Floyd-Warshall 演算法一樣，這里仍然 使用二維數組 e 來存儲頂點之間邊的關系， 初始值如下。

我們還需要用 一個一維數組 dis 來存儲 1 號頂點到其餘各個頂點的初始路程， 我們可以稱 dis 數組為 「距離表」， 如下。

我們將此時 dis 數組中的值稱為 最短路的「估計值」。

既然是 求 1 號頂點到其餘各個頂點的最短路程， 那就 先找一個離 1 號頂點最近的頂點。

通過數組 dis 可知當前離 1 號頂點最近是 2 號頂點。 當選擇了 2 號頂點後，dis[2]的值就已經從「估計值」變為了「確定值」， 即 1 號頂點到 2 號頂點的最短路程就是當前 dis[2]值。

為什麼呢？你想啊， 目前離 1 號頂點最近的是 2 號頂點，並且這個圖所有的邊都是正數，那麼肯定不可能通過第三個頂點中轉，使得 1 號頂點到 2 號頂點的路程進一步縮短了。 因此 1 號頂點到其它頂點的路程肯定沒有 1 號到 2 號頂點短，對吧 O(∩_∩)O~

既然選了 2 號頂點，接下來再來看 2 號頂點 有哪些 出邊 呢。有 2->3 和 2->4 這兩條邊。

先討論 通過 2->3 這條邊能否讓 1 號頂點到 3 號頂點的路程變短。 也就是說現在來比較 dis[3] 和 dis[2]+e[2][3] 的大小。其中 dis[3]表示 1 號頂點到 3 號頂點的路程，dis[2]+e[2][3]中 dis[2]表示 1 號頂點到 2 號頂點的路程，e[2][3]表示 2->3 這條邊。所以 dis[2]+e[2][3]就表示從 1 號頂點先到 2 號頂點，再通過 2->3 這條邊，到達 3 號頂點的路程。

我們發現 dis[3]=12，dis[2]+e[2][3]=1+9=10，dis[3]>dis[2]+e[2][3]，因此 dis[3]要更新為 10。這個過程有個專業術語叫做 「鬆弛」 。即 1 號頂點到 3 號頂點的路程即 dis[3]，通過 2->3 這條邊 鬆弛成功。 這便是 Dijkstra 演算法的主要思想： 通過 「邊」 來鬆弛 1 號頂點到其餘各個頂點的路程。

同理通過 2->4（e[2][4]），可以將 dis[4]的值從 ∞ 鬆弛為 4（dis[4]初始為 ∞，dis[2]+e[2][4]=1+3=4，dis[4]>dis[2]+e[2][4]，因此 dis[4]要更新為 4）。

剛才我們對 2 號頂點所有的出邊進行了鬆弛。鬆弛完畢之後 dis 數組為：

接下來，繼續在剩下的 3、4、5 和 6 號頂點中，選出離 1 號頂點最近的頂點。通過上面更新過 dis 數組，當前離 1 號頂點最近是 4 號頂點。此時，dis[4]的值已經從「估計值」變為了「確定值」。下面繼續對 4 號頂點的所有出邊（4->3，4->5 和 4->6）用剛才的方法進行鬆弛。鬆弛完畢之後 dis 數組為：

繼續在剩下的 3、5 和 6 號頂點中，選出離 1 號頂點最近的頂點，這次選擇 3 號頂點。此時，dis[3]的值已經從「估計值」變為了「確定值」。對 3 號頂點的所有出邊（3->5）進行鬆弛。鬆弛完畢之後 dis 數組為：

繼續在剩下的 5 和 6 號頂點中，選出離 1 號頂點最近的頂點，這次選擇 5 號頂點。此時，dis[5]的值已經從「估計值」變為了「確定值」。對5號頂點的所有出邊（5->4）進行鬆弛。鬆弛完畢之後 dis 數組為：

最後對 6 號頂點的所有出邊進行鬆弛。因為這個例子中 6 號頂點沒有出邊，因此不用處理。 到此，dis 數組中所有的值都已經從「估計值」變為了「確定值」。

最終 dis 數組如下，這便是 1 號頂點到其餘各個頂點的最短路徑。

OK，現在來總結一下剛才的演算法。 Dijkstra演算法的基本思想是：每次找到離源點（上面例子的源點就是 1 號頂點）最近的一個頂點，然後以該頂點為中心進行擴展，最終得到源點到其餘所有點的最短路徑。

基本步驟如下：

在 博客 中看到兩個比較有趣的問題，也是在學習Dijkstra時，可能會有疑問的問題。

當我們看到上面這個圖的時候，憑借多年對平面幾何的學習，會發現在「三角形ABC」中，滿足不了 構成三角形的條件(任意兩邊之和大於第三邊)。 納尼，那為什麼圖中能那樣子畫？

還是「三角形ABC」，以A為起點，B為終點，如果按照平面幾何的知識， 「兩點之間線段最短」， 那麼，A到B的最短距離就應該是6(線段AB)，但是，實際上A到B的最短距離卻是3+2=5。這又怎麼解釋？

其實，之所以會有上面的疑問，是因為 對邊的權值和邊的長度這兩個概念的混淆， 。之所以這樣畫，也只是為了方便理解（每個人寫草稿的方式不同，你完全可以用別的方式表示，只要便於你理解即可）。

PS：數組實現鄰接表可能較難理解，可以看一下 這里

參考資料：

Dijkstra演算法是一種基於貪心策略的演算法。每次新擴展一個路程最短的點，更新與其相鄰的點的路程。當所有邊權都為正時，由於不會存在一個路程更短的沒擴展過的點，所以這個點的路程永遠不會再被改變，因而保證了演算法的正確性。

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

那麼，有沒有可以求帶負權邊的指定頂點到其餘各個頂點的最短路徑演算法（即「單源最短路徑」問題）呢？答案是有的， Bellman-Ford演算法 就是一種。（我們已經知道了 Floyd-Warshall 可以解決「多源最短路」問題，也要求圖的邊權均為正）

通過 鄰接矩陣 的Dijkstra時間復雜度是 。其中每次找到離 1 號頂點最近的頂點的時間復雜度是 O(N)，這里我們可以用 優先隊列（堆） 來優化，使得這一部分的時間復雜度降低到 。這個我們將在後面討論。

⑥ 迪克斯特拉演算法結果怎麼看解釋一下

這個演算法最後的結果就是一旁信個點到圖中每一個點的最短距離。比如一個圖中有A,B,C,D,E,F,G七個點，你要求A到轎祥其他每一個點的最短距離，那麼最後的結果應該是類似A到B最短距離XXX，A到C最短距離XXX，A到D最短距離XXX，閉啟搏……
應該是很簡單的。
題主你為什麼看不懂？

⑦ 【數據結構】最短路徑之迪傑斯特拉(Dijkstra)演算法與弗洛伊德(Floyd)演算法

迪傑斯特拉(Dijkstra)演算法核心： 按照路徑長度遞增的次序產生最短路徑。

迪傑斯特拉(Dijkstra)演算法步驟：（求圖中v0到v8的最短路徑）並非一下子求出v0到v8的最短路徑，而是 一步一步求出它們之間頂點的最短路徑 ，過過程中都是 基於已經求出的最短路徑的基礎上，求得更遠頂點的最短路徑，最終得出源點與終點的最短路徑 。

弗洛伊德(Floyd)演算法是一個經典的 動態規劃演算法 。

⑧ dijkstra演算法是什麼

迪傑斯特拉演算法用來解決從頂點v0出發到其餘頂點的最短路徑，該演算法按照最短路徑長度遞增的順序產生所以最短路徑。

對於圖G=（V，E），將圖中的頂點分成兩組：第一組S：已求出的最短路徑的終點集合（開始為｛v0}）。第二組V-S：尚未求出最短路徑的終點集合（開始為V-{v0}的全部結點）。

堆優化

思考

該演算法復雜度為n^2,我們可以發現，如果邊數遠小於n^2,對此可以考慮用堆這種數據結構進行優化，取出最短路徑的復雜度降為O(1)；每次調整的復雜度降為O（elogn）；e為該點的邊數，所以復雜度降為O((m+n)logn)。

實現

1、將源點加入堆，並調整堆。

2、選出堆頂元素u（即代價最小的元素），從堆中刪除，並對堆進行調整。

3、處理與u相鄰的，未被訪問過的，滿足三角不等式的頂點

1):若該點在堆里，更新距離，並調整該元素在堆中的位置。

2):若該點不在堆里，加入堆，更新堆。

4、若取到的u為終點，結束演算法；否則重復步驟2、3。

⑨ 迪傑斯特拉演算法的本質是貪心還是動態規劃

我認為 Dijkstra演算法 的本質是 廣度優先搜索，
而此處的廣度是定義在路程的cost之上的。
（就好比從圓心處向外擴散一個圓環，首次碰到的就是最近）

動態規劃泛指，重疊子問題與原問題的推算關系（學名：動態轉移方程），
貪心是極端情況的斗升蘆動態規劃，子問題獨一選擇性。

Dijkstra演算法的分解思路是
到達某節點的cost最小路徑 --（從這裡面選）--> { 到達其相鄰節點的cost最小路徑 }
獨一選擇性:
只挑選空帶： Min {到達其相鄰節點笑並的最短路徑}

結論：的確是貪心策略

請採納。

⑩ 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到任何其他頂點的最短路徑。