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相对较大的叫稠密图），我们可以考虑用另外一种表示方式来代替我们一直在用的 邻接矩阵 —— 邻接表