dijkstra演算法步驟例題

『壹』 最短路徑 - Dijkstra演算法

演算法每次都查找距離起始點最近的點，那麼剩下的點距離起始點的距離一定比當前點大。

1.選定A節點並初始化，如上述步驟3所示

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演算法保證能找到一條從初始點到目標點的最短路徑，只要所有的邊都有一個非負的代價值。在上圖中，粉紅色的結點是初始結點，藍色的是目標點，而類菱形的有色區域則是Dijkstra演算法掃描過的區域。顏色最淡的區域是那些離初始點最遠的，因而形成探測過程（exploration）的邊境（frontier）。因而Dijkstra演算法可以找到一條最短的路徑，但是效率上並不高。

數據結構--Dijkstra演算法最清楚的講解

『貳』 用dijkstra演算法計算源點到個結點的最短路徑....謝謝親愛的朋友~ 詳細答案

(這里描述的是從節點1開始到各點的dijkstra演算法，其中Wa->b表示a->b的邊的權值，d(i)即為最短路徑值)
1． 置集合S={2,3,...n}, 數組d(1)=0, d(i)=W1->i(1,i之間存在邊) or +無窮大(1.i之間不存在邊) 2． 在S中，令d(j)=min{d(i),i屬於S}，令S=S-{j}，若S為空集則演算法結束，否則轉3
3． 對全部i屬於S,如果存在邊j->i，那麼置d(i)=min{d(i), d(j)+Wj->i}，轉2

『叄』 最短路徑演算法（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演算法（迪傑斯特拉演算法）是很有代表性的最短路徑演算法，用於計算一個結點到其他結點的最短路徑。該演算法指定一個點（源點）到其餘各個結點的最短路徑，因此也叫做單源最短路徑演算法。該演算法是由荷蘭計算機科學家Edsger W.Dijkstra於1959年發表。
Dijkstra演算法是一種用於計算帶權有向圖中單源最短路徑演算法，不存在回溯的過程，因此它還不適用於帶有負權重的情況。如果權值存在負數，那麼被派生出來的可能是更短的路徑，這就需要過程可以回溯，之前的路徑需要被更短的路徑替換掉，而Dijkstra演算法是不能回溯的，它的每一步都是以當前最優選擇為前提的。
Dijkstra演算法的思想是廣度優先搜索（BFS） 貪心策略。對於計算非加權圖中的最短路徑，也可使用BFS演算法。Dijkstra演算法是對BFS演算法的推廣，以起始點為中心向外層層擴展，並且每一次都選擇最優的結點進行擴展，直到擴展到終點為止。Dijkstra演算法可以劃歸為貪心演算法，下一條路徑都是由當前更短的路徑派生出來的更長的路徑。
Dijkstra演算法在很多專業課程中都作為基本內容有詳細的介紹，如數據結構、圖論、運籌學等。
二、演示例子例子1
第1步，創建距離表。第1列是結點名稱，第2列是從起點A到對應結點的已知最短距離。開始我們並不知道A到其它結點的最短距離是多少，默認初始距離是無窮大。如圖2-1-1所示：
圖2-1-1
第2步，遍歷起點A的所有相鄰結點，找到起點A的鄰接結點B和C。從A到B的距離是5，從A到C的距離是2，刷新距離表中起點A到各結點的最短距離(綠色表示刷新)。如圖2-1-2所示。
圖2-1-2
第3步，從圖2-1-2距離表中找到從A出發距離最短的點，也就是結點C（最小距離是2）。遍歷結點C的所有相鄰結點，找到結點C的相鄰結點D和F（A已經遍歷過，不需要考慮）。從C到D的距離是1，所以A到D的距離是A-C-D=2 1=3；從C到F的距離是8；從A到F的距離是A-C-F=2 8=10。然後刷新距離表(綠色表示刷新)。如圖2-1-3所示：
圖2-1-3
第4步，從圖2-1-3距離表中找到從A出發距離最短的點（紅色結點C已經遍歷過，不需要考慮），也就是結點D（最小距離是3）。遍歷結點D的所有相鄰結點，找到相鄰結點B、E和F（C已遍歷過，不考慮）。從A-C-D-B的距離是3 1=4；從A-C-D-E的距離是3 1=4；從A-C-D-F的距離是3 2=5。刷新距離表中起點A到各結點的最短距離。如圖2-1-4所示。
圖2-1-4
第5步，從圖2-1-4距離表中找到從A出發距離最短的點（紅色結點C、D已經遍歷過，不需要考慮），也就是結點B和E（最小距離是4）。遍歷結點B的所有相鄰結點，找到相鄰結點E(D遍歷過，不考慮),從A-C-D-B-E的距離為10，比當前A到E的最小距離4要大，不考慮。遍歷結點E的所有相鄰結點，找到相鄰結點G、B(D遍歷過，不考慮),從A-C-D-E-G的距離為4 7=114,不考慮。如圖2-1-5所示。
圖2-1-5
第6步，從圖2-1-5距離表中找到從A出發距離最短的點（紅色結點B、C、D、E已經遍歷過，不需要考慮），也就是結點F（最小距離是5）。從A-C-D-F-G的距離為8, 比當前最小距離11要小，刷新距離表。如圖2-1-6所示。
圖2-1-6
就這樣，除終點以外的全部結點都已經遍歷完畢，距離表中存儲的是從起點A到所有結點的最短距離。
例子2
圖2-2-1是原始連通圖。
圖2-2-1
用Dijkstra演算法找出以A為起點的單源最短路徑步驟如下：

步驟
集合S
集合Q
1
選擇A到集合S={A}
此時最短路徑A->A=0
以A為中間點，查找相鄰點
Q={B,C,D,E,F,G}
A->-B=5
A->C=2
A->其它Q中結點=∞
發現A->C=2權值為最短
2
選擇C到S={A,C}
此時最短路徑A->A=0,A->C=2
以C為中間點，從A->C這條路徑開始找
Q={B,D,E,F,G}
A->B=5(由第1步得到)
A->C->D=3
A->C->F=10
A->C->其它Q中結點=∞
在A到Q的結點中，發現A->C->D=3權值為最短
3
選擇D到S={A,C,D}
此時最短路徑A->A=0,A->C=2,A->C->D=3,
以D為中間點，從A->C->D這條路徑開始找
Q={B,E,F,G}
A->C->D->B=4(比第1步的A->B=5要短，替換之)
A->C->D->E=4
A->C->D->F=5(比第2步的A->C->F=10要短，替換之)
A->C->D->G=∞
在A到Q的結點中，發現A->C->D->B=4或A->C->D->E=4權值為最短
4
選擇B、E到S={A,C,D,B,E}
此時最短路徑A->A=0,A->C=2,A->C->D=3,A->C->D->B=4,A->C->D->E=4,
以B、E為中間點，分別從A->C->D->B、從A->C->D->E路徑開始找
Q={F,G}
A->C->D->E->G=11
A->C->D->F=5(從第3步獲得)
在A到Q的結點中，發現A->C->D->F權值為最短
5
選擇F到S={A,C,D,B,E,F}
此時最短路徑A->A=0,A->C=2,A->C->D=3,A->C->D->B=4,A->C->D->E=4,A->C->D->F=5
以F為中間點，從,A->C->D->F這條路徑開始找
Q={G}
A->C->D->F->G=8(比第4步的A->C->D->E->G=11要短，替換之)
6
選擇G到S={A,C,D,B,E,F,G}
此時最短路徑A->A=0,A->C=2,A->C->D=3,A->C->D->B=4,A->C->D->E=4,A->C->D->F=5,A->C->D->F->G=8
集合Q為空，查找完畢。

例子3
Dijkstra演算法的執行過程：設初始集合S={s}, Q={t,y,x,z}. 源結點s為最左邊的結點，每個結點中（圓圈中）的數值為該結點的最短路徑的估計值（當前中間值）。黑色的結點屬於集合S，白色的結點屬於集合Q。每次從集合 S中選擇最新加入的結點，分別計算並刷新與它直接相鄰的結點的最短路徑的估計值，然後從集合Q中選擇最小估計值的結點，加入到集合S中。例如(b)中，集合Q中刷新後各結點的估計值為10，5，∞，∞，選擇最小估計值為5的結點y，加入到集合S中, 接著計算並刷新結點y的相鄰結點的最短路徑的估計值。依次類推，直到集合Q中的所有結點全部加入到集合S中，演算法結束。如圖2-3-1所示。
圖2-3-1
三、應用
一切能抽象成圖或樹的場景，如果要求最短路徑，Dijkstra演算法可考慮。比如，查找兩個城市之間的最短路徑；在地圖中尋找兩個地點之間的最短路徑；在網路連接中為路由器尋找最短的傳輸路徑等。

『伍』 利用Dijkstra演算法求下圖中從頂點1到其它各頂點間的最短路徑，按下面表格形式

v1到v2：10為最短路徑；

v1到v3：7為最短路徑；

v1到v4：8為最短路徑；

v1到v5：v1-> v2 -> v5 =10+6= 16；v1v3v5=7+9=16;v1v4v6v5=8+5+2=15; 15為最短路徑；

v1到v6：v1v2v3v6=10+2+9=21；v1v3v6=7+9=16；v1v4v6=8+5=13；13為最短路徑；

v1到v7：v1v2v5v7=10+6+20=36；v1v3v5v7=7+9+20=36；v1v3v6v7=7+9+30=46；

v1v4v6v7=8+5+30=42；v1v4v6v5v7=35；35為最短路徑

Dijkstra：

求單源、無負權的最短路。時效性較好，時間復雜度為O（V*V+E）。源點可達的話，O（V*lgV+E*lgV）=>O（E*lgV）。當是稀疏圖的情況時，此時E=V*V/lgV，所以演算法的時間復雜度可為O（V^2）。若是斐波那契堆作優先隊列的話，演算法時間復雜度，則為O（V*lgV + E）。

以上內容參考：網路-最短路徑演算法