Dijkstra單源最短路徑
圖
這里求定點A到各頂點的最短距離？
0
我們需要有一個數組記錄當前已知的從頂點A到各頂點的最小距離：
1.png
1 (第一輪)
從當前數組中找到一個離A頂點最近的頂點，即B （A->B = 2）。當選擇了B頂點之后，A->B 也就是Dis[B]的值就從“估計值”變成了“確定值”。為什么呢？因為目前離A頂點最近的頂點已經是B了，圖中并不存在負值的路徑，就不可能有第三個點X使得 A->X->B 的距離小于當前的 A->B 的距離；如果存在這樣一個點X的話，那么當前距離頂點A最近的點就不是B了，而是X。
2
既然選定了頂點B，那么我們可以看到B訂單有兩條出邊：
- B -> C : 9
- B -> D : 3
這時我們想，既然B有到C、D的出邊，那么從A到C、D是否會通過B頂點而變短呢（畢竟當前A->B的距離是已經是確信最短的了），所以我們比較：
- Dis[C]=
12和 Dis[B]+Map[B][C]=10 - Dis[D]=
&和 Dis[B]+Map[B][D]=4
結果我們發(fā)現A->C 和 A->D 的距離因為加入了B頂點中轉使得距離變短，因此，我們可以更新頂點A的最小距離數組：
2.png
這個過程叫做 “松弛”
4 (第二輪)
這時我們可以重復 1 的操作，cong從當前數組中的“估計值”（也就是 C、D、E、F）中找到離A最近的頂點，即D。同樣Dis[D]的值從“估計值”變成了“確定值”。
5
D頂點的出邊：
- D -> C : 4
- D -> E : 13
- D -> F : 15
通過D頂點來對qi其出邊上的頂點進行松弛
- Dis[C]=
8和 Dis[D]+Map[D][C]=13 - Dis[E]=
&和 Dis[D]+Map[D][E]=17 - Dis[F]=
&和 Dis[D]+Map[D][F]=19
我們來更新頂點A的最小距離數組：
3.png
6 (第三輪)
4.png
7 (第四輪)
5.png
8 (第五輪)
6.png
func Dijkstra() {
// 999表示頂點之間沒有連通
var theMap = [6][6]int{
{0, 1, 12, 999, 999, 999},
{999, 0, 9, 3, 999, 999},
{999, 999, 0, 999, 5, 999},
{999, 999, 4, 0, 13, 15},
{999, 999, 999, 999, 0, 4},
{999, 999, 999, 999, 999, 0},
}
var marks = [6]int{1, 0, 0, 0, 0, 0} // 1，表示該頂點最短路徑為確定值；0，表示該頂點的最短路徑為估計值
var dis [6]int
// 初始化A頂點的最小路徑數組
for i := 0; i < 6; i++ {
dis[i] = theMap[0][i]
}
fmt.Println("Dijkstra")
// Dijkstra
for i := 0; i < 5; i++ { // 這里為6個頂點，所以總共要進行5次 “松弛”
minDistance := 1000 // 記錄一次松弛中“估計值”中的最小距離
currentPoint := 0 // 記錄一次松弛中“估計值”中的頂點
// 遍歷最短距離數組，找到“估計值”中距離A頂點最近的頂點
for j := 0; j < len(dis); j++ { //
if marks[j] == 0 && minDistance > dis[j] {
minDistance = dis[j]
currentPoint = j
}
}
marks[currentPoint] = 1 // 標記最小“估計值”為“確認值”
// 遍歷該頂點的出邊并進行松弛
for k := 0; k < 6; k++ {
if theMap[currentPoint][k] < 999 && dis[k] > (dis[currentPoint]+theMap[currentPoint][k]) {
dis[k] = dis[currentPoint] + theMap[currentPoint][k]
}
}
}
fmt.Println("Dijkstra A -> ... ", dis)
}
結果
這個算法的時間復雜度是 O(N2)，其中每次尋找離A頂點最近的頂點的時間復雜度是O(N)，我們可以用“堆”來優(yōu)化這部分，將這部分復雜度優(yōu)化到O(logN)；
另外，我們考慮到在圖中，邊數M 通常是遠小于N2的（這種圖叫稀疏圖，M相對較大的叫稠密圖），我們可以考慮用另外一種表示方式來代替我們一直在用的 鄰接矩陣 —— 鄰接表
