求單源最短路徑用得最多的算法應該就是Dijstra算法了，但是該算法有一個缺點就是不能處理負權，如果遇到負權大家可以參考后面介紹的BellMan Ford算法進行處理。

下面介紹下Dijstra算法的主要步驟：

1. 初始化集合U，該集合表示已經入選最小的節點集合

2. 初始化D，該數組表示源點s到該點的最小距離，沒有直接相連則視為無窮大

3. 選出距離源點最小距離的點w

4. 對直接與w點相連的點進行處理，D[v] ← min(D[v], D[w] + A[w][v])：即對與w點直接相連的點，如果存在一條更短路勁達到該點，則刷新該點的D值。

?

Dijkstra(s, A, D) U = {s};for each vertex vD[v] ← A[s][v]while U ≠ VSelect vertex w ∈ V-U with minimum D[w]U ← U ∪ {w}for each vertex v adjacent to wD[v] ← min(D[v], D[w] + A[w][v])

?

?

?

轉載于:https://www.cnblogs.com/xfei-zhang/p/5086882.html

總結

以上是生活随笔為你收集整理的图---Dijstra的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。