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
结果我们发现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)，我们可以用“堆”来优化这部分，将这部分复杂度优化到O(logN)；
另外，我们考虑到在图中，边数M 通常是远小于N2的（这种图叫稀疏图，M相对较大的叫稠密图），我们可以考虑用另外一种表示方式来代替我们一直在用的 邻接矩阵 —— 邻接表
