Dijkstra單源最短路徑
這里求定點A到各頂點的最短距離？
0
我們需要有一個數(shù)組記錄當(dāng)前已知的從頂點A到各頂點的最小距離：
1 (第一輪)
從當(dāng)前數(shù)組中找到一個離A頂點最近的頂點萧落，即B （A->B = 2）珊随。當(dāng)選擇了B頂點之后，A->B 也就是Dis[B]的值就從“估計值”變成了“確定值”污淋。為什么呢顶滩？因為目前離A頂點最近的頂點已經(jīng)是B了，圖中并不存在負值的路徑寸爆，就不可能有第三個點X使得 A->X->B 的距離小于當(dāng)前的 A->B 的距離礁鲁；如果存在這樣一個點X的話，那么當(dāng)前距離頂點A最近的點就不是B了赁豆，而是X仅醇。
2
既然選定了頂點B，那么我們可以看到B訂單有兩條出邊：
- B -> C : 9
- B -> D : 3
這時我們想歌憨，既然B有到C着憨、D的出邊，那么從A到C务嫡、D是否會通過B頂點而變短呢（畢竟當(dāng)前A->B的距離是已經(jīng)是確信最短的了）甲抖，所以我們比較：
- Dis[C]=
12和 Dis[B]+Map[B][C]=10 - Dis[D]=
&和 Dis[B]+Map[B][D]=4
結(jié)果我們發(fā)現(xiàn)A->C 和 A->D 的距離因為加入了B頂點中轉(zhuǎn)使得距離變短，因此心铃，我們可以更新頂點A的最小距離數(shù)組：
這個過程叫做 “松弛”
4 (第二輪)
這時我們可以重復(fù) 1 的操作准谚，cong從當(dāng)前數(shù)組中的“估計值”（也就是 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的最小距離數(shù)組：
6 (第三輪)
7 (第四輪)
8 (第五輪)
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頂點的最小路徑數(shù)組
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 // 記錄一次松弛中“估計值”中的頂點
// 遍歷最短距離數(shù)組，找到“估計值”中距離A頂點最近的頂點
for j := 0; j < len(dis); j++ { //
if marks[j] == 0 && minDistance > dis[j] {
minDistance = dis[j]
currentPoint = j
}
}
marks[currentPoint] = 1 // 標(biāo)記最小“估計值”為“確認(rèn)值”
// 遍歷該頂點的出邊并進行松弛
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)
}
這個算法的時間復(fù)雜度是 O(N2)王浴，其中每次尋找離A頂點最近的頂點的時間復(fù)雜度是O(N)脆炎，我們可以用“堆”來優(yōu)化這部分，將這部分復(fù)雜度優(yōu)化到O(logN)氓辣；
另外秒裕，我們考慮到在圖中，邊數(shù)M 通常是遠小于N2的（這種圖叫稀疏圖钞啸，M相對較大的叫稠密圖）几蜻，我們可以考慮用另外一種表示方式來代替我們一直在用的 鄰接矩陣 —— 鄰接表
