【经典算法】最短路径算法—

🌈 个人主页：十二月的猫-CSDN博客
🔥 系列专栏： 🏀算法启示录

💪🏻 十二月的寒冬阻挡不了春天的脚步，十二点的黑夜遮蔽不住黎明的曙光

前言

松弛视角

伪代码展示

三角形理论

松弛操作可行性证明

迪杰斯特拉(Dijkstra)

一前言

二算法介绍

三算法比较

四核心思想

五算法步骤

六注意事项

七伪代码

总结

前言

最短路径算法是图论中一类重要算法，其功能就如名字一样——求解点与点之间最短距离。

首先，先让我们对最短路径算法有一个概观，看看都有哪些种类的最短路径算法，每一个种类中代表的算法又是什么。

单源最短路径算法：从一个起点出发求解其到其他所有其他点的最短距离

多源最短路径算法：从所有点出发求解其到其他所有其他点的最短距离

本篇的迪杰斯特拉算法就属于单源最短路径算法

松弛视角

关键点：

1、松弛和动态规划都是解决最短路径的方法。

2、松弛的本质就是对图固有属性三角理论的修正。

3、松弛和动态规划方法存在一定的重合，有时可以相互转化。两者并未有固定的优秀等次之分。

4、一些算法采用松弛视角解决，另一些采用动态规划视角来解决

伪代码展示

最短路径的求解包含两个步骤：一、初始化操作；二、松弛操作

松弛是最短路径求解过程中最好用的手段之一

两个操作的伪代码如下：

初始化操作：

INITIALIZE(G,s)
    for each vertex v ∈ G.V
        v.d=∞
        v.π=NULL
    s.d=0

松弛操作：

RELAX(u,v,w)
    if v.d>u.d+w(u,v)
        v.d=u.d+w(u,v)
        v.π=u

松弛操作的本质是对三角形理论的修正

三角形理论

定义：

对于任何边（u，v）∈E，都有d(s,v)<=d(s,u)+w(u,v)

d(s,v)表示s到v的最短路径

任何图都满足三角形理论，三角形理论是图形的固有性质

松弛操作可行性证明

既然三角形理论是任何图形的固有性质。那么一旦一个图形中的出发源点s到目的点v的距离不符合三角形理论，那么就说明d(s,v)是不准确的（偏大），或者d(s,u)是不准确的（偏小）。显然我们初始化时令d(s,v)都是正无穷，所以d(s,u)偏小是不可能的。因此必然是d(s,v)偏大，需要修正。此时我们就令v.d=u.d+w(u,v)，从而完成对d(s,v)的修正。

如果顶点v到s的距离满足三角形理论，那么此时的距离可能是正确的（即最短距离）。如果顶点v到s的距离经过所有其他顶点的三角形理论检验仍然满足，则说明此时得到的一定是正确的（即一定是最短距离）。

一次次的修正（松弛），点与点之间距离不断减少，直到最后得到最短路径。这就是松弛操作求解最短路径的可行性证明

较难理解！！但是希望大家可以好好看一遍

迪杰斯特拉(Dijkstra)

一前言

动态规划和贪婪算法的一种不严谨的直观认识：

动态规划做出的结果在一次次循环中会发生改变；贪婪算法每次做出的结果（局部最优）就是全局最优，不会再发生改变

二算法介绍

迪杰斯特拉算法是由荷兰计算机科学家在1956年发现的算法，此算法使用类似广度优先搜索的方法解决了带权图的单源最短路径问题。它是一个贪心算法

三算法比较

与贝尔曼福特算法：

一、算法类型不同

迪杰斯特拉算法也是单源最短路径求解算法之一，和贝尔曼福特算法有相似的用途。不同的是贝尔曼福特算法是动态规划算法，前面做出的选择在后面可能更改；但是迪杰斯特拉算法是贪婪算法，每次做出的选择都是全局最优的，不会反复更改。

二、算法使用条件不同

迪杰斯特拉算法相比于贝尔曼福特算法是一种更特殊的算法，它只能用于没有负权重的带权图。而贝尔曼福特算法的适用图可以存在负权重，只是不能存在负权重回路。

三、算法运行效率不同

迪杰斯特拉算法是贪婪算法，所以运行效率高于贝尔曼福特算法

与BFS算法：

一、算法使用条件不同

广度优先搜索算法能够生成一棵树，并且这棵树上的所有点到树根的距离都是最短路径。但是BFS算法不可以处理存在权重的图，仅仅用于无权重的图

二、算法运行效率不同

BFS算法时间复杂度为O(V+E)；迪杰斯特拉算法时间复杂度为O（VlgV+E)；贝尔曼福特算法时间复杂度为O(VE)。考虑到一般情况下：E=V^2，所以贝尔曼福特算法复杂是最高的，其次是迪杰斯特拉算法，最后是BFS算法

注意点：在迪杰斯特拉和BFS算法中，E前面都不用乘V。但是在算法实现上，对边的访问是嵌套在点的访问V内的。要理解这个点，需要注意到对边的访问不是所有的边，而是点的邻边，这就代表遍历完所有点，访问的边也仅仅是E。所以这里E前面不用乘V

上面这三个时间复杂度，大家务必记住！！！最好能够理解，自己推导

四核心思想

贪心策略：

每次选择一个点，这个点满足两个条件：1、未被访问过；二、到源点距离最短

这个点就是一个全局最优解！后续这个点到源点的距离是不需要修改的！！

贪心选择后的处理：

每次做出贪心选择后，贪心策略会影响后面子问题的最优解，所以在一些贪心问题中需要进行贪心选择后处理（贪心算法的必要条件是贪心选择后子问题仍有最优解）

处理：对于这个点的所有邻近点去尝试松弛

五算法步骤

首先，设置两个集合A和B。A用来存放已经求出最短路径的点，B用来存放未计算最短路径的点（B中的点分为两类：一类无法到源点；另一类已经可以到源点但是不一定是最短路径）。其中B=V-A，实际上变量集合只有A一个。接下来就来做题吧~~~

假设题目如下：

初始步：创建表格，将表格中所有点到源点的距离都设置为正无穷，顶点0到源点的距离设置为0

第一步：贪婪选择顶点0，加入集合A，得到 A集合为：{0}，B集合为：{1，2，3，4，5，6}

第二步：对和0邻接的所有点的执行松弛操作，此时，因为与0邻接的有1和2，并且到这两个点的距离，小于原来的∞距离，所以要将这两个点到0的距离都进行更新，如下图：

第三步：从集合B{1，2，3，4，5，6}中，贪婪选择顶点2，加入集合A，得到 A集合为：{0，2}，B集合为：{1，3，4，5，6}，如下图：

第四步：对和顶点2邻接的所有点的执行松弛操作，此时，因为与2邻接的有3和5，并且到这两个点的距离，小于原来的∞距离，所以要将这两个点到0的距离都进行更新，如下图：

后续操作和前面四步是相同的，直到所有点进入集合A算法停止

总结起来就是：

第一步：在距离表格中，贪婪选择新的点，将点加入集合A，得到全新的集合A和B

第二步：对与新点邻接的边执行松弛操作，得到新的表格

六注意事项

1.不能处理带有负权边的图(可能得不到最优解，认为是无法处理负权图)，只能处理非负权图

如上图，更新顺序为：更新1，更新3，更新2。此时更新2后1的值更小了，这显然不符合贪婪选择（局部最优就是全局最优的结论）

2.只能解决单源最短路径问题

七伪代码

DIJKSTRA(G,w,s) //s用来记录访问的顺序，是需要返回的值；w边的权重集合
    S=空集合
    Q=G.V
    while(Q <> 空集合）
        u=EXTRACT-MIN(Q)
        S=S U {u}
        for each vertex v∈G.adj[u]
            RELEX(u,v,w)