数据结构与算法——图最短路径

﹏ヽ暗。殇╰゛Y 2022-04-24 05:52 228阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

## 1 引言 ##

**最短路径问题**一直是图论研究的热点问题。例如在实际生活中的路径规划、地图导航等领域有重要的应用。关于求解图的最短路径方法也层出不穷，本篇文章将详细讲解图的最短路径经典算法。

## 2 重要概念 ##

**图的路径：**图G =中，从任一顶点开始，由边或弧的邻接至关系构成的有限长顶点序列称为路径。  
  注意：有向图的路径必须沿弧的方向构成顶点序列；构成路径的顶点可能重复出现(即允许反复绕圈)。  
  **路径长度：**路径中边或弧的数目。  
  **简单路径：**除第一个和最后一个顶点外，路径中无其它重复出现的顶点，称为简单路径。  
  **回路或环：**路径中的第一个顶点和最后一个顶点相同时，称为回路或环。  
  **图的最短路径：**如果从有向图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。

## 3 深度或广度优先搜索算法 ##

### 3.1 算法概述 ###

从起点开始访问所有深度遍历路径或广度优先路径，则到达终点节点的路径有多条，取其中路径权值最短的一条则为最短路径。

### 3.2 算法流程 ###

（1）选择单源的起点作为遍历的起始点。  
    
  （2）采用深度优先搜索或者广度优先搜索的方式遍历图，在遍历同时记录可以到达终点的路径。  
    
  （3）在所有路径中选择距离最短的路径。

### 3.3 实例图解 ###

例如：图3.3.1所示的有向图中，选取A为源点，D为终点，采用遍历的方式获取最短路径。

![640?wx\_fmt=png][640_wx_fmt_png] 图3.3.1

（1）选择A为遍历起始点，D为终点。

（2）采用遍历的方式获取A到D路径。通过遍历方式得到的路径共有5条。

（3）从中选择距离最短的路径为A->B->D，长度为9。

### 3.4 算法分析 ###

采用遍历的方式获取单源最短路径，是一种暴力破解的方式。算法的性能与遍历过程性能相关。采用深度优先搜索遍历时时间复杂度为O(n+e)。

## 4 迪杰斯特拉（Dijkstra）算法 ##

### 4.1 算法概述 ###

Dijkstra（迪杰斯特拉）算法是典型的单源最短路径算法，用于计算某个顶点到其他所有顶点的最短路径。Dijkstra（迪杰斯特拉）算法要求图中不存在负权边，即保证图中每条边的权重值为正。算法的基本思想是：从源点出发，每次选择离源点最近的一个顶点前进，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。

### 4.2 算法流程 ###

（1）将所有的顶点分为两部分：已知最短路程的顶点集合P和未知最短路径的顶点集合Q。最开始，已知最短路径的顶点集合P中只有源点s一个顶点。我们这里用一个book\[i\]数组来记录哪些点在集合P中。例如对于某个顶点i，如果book\[i\] = 1则表示这个顶点在集合P中，如果book\[i\] = 0则表示这个顶点在集合Q中。  
  （2）设置源点s到自己的最短路径为0即dist = 0。若存在源点有能直接到达的顶点i，则把dist\[i\]设为e\[s\]\[i\]。同时把所有其它（即源点不能直接到达的）顶点的最短路径为设为∞。  
  （3）在Q中选择一个离源点s最近的顶点u（即dist\[u\]最小）加入到P中。并考察所有以点u为起点的边，对每一条边进行松弛操作。  
  （4）重复第3步，如果集合Q为空，算法结束。最终dist数组中的值就是源点到所有顶点的最短路径。

### 4.3 实例图解 ###

例如：图4.3.1所示的有向图，以顶点1为源点，运用Dijkstra算法，获得最短路径。

![640?wx\_fmt=png][640_wx_fmt_png 1] 图4.3.1

（1）初始状态下，集合P中只有顶点1， book\[1\]=1。book数组以及dist数组如图：

（2）从dist数组中可以看出，距离顶点1最近的顶点为2，不存在可以中转的顶点使得顶点1到顶点2的距离更短，且顶点2不在集合P中。因此，选择顶点2加入集合P中，令book\[2\]=1。顶点2加入后，需要考虑经过顶点2进行中转，使得顶点1到达其余顶点的距离发生改变。顶点2的出边有<2,3>和<2,4>。则需重新计算dist\[3\]和dist\[4\]。dist\[3\] = dis\[2\]+e\[2\]\[3\] = 10 < 12，令dist\[3\]松弛为12。dist\[4\] = dis\[2\]+e\[2\]\[4\] = 4 < INF，令dist\[4\]松弛为4。更新后的book数组和dist数组如下：

（3）从剩余顶点3、4、5、6中选择dist中最近顶点为顶点4（因为顶点2已经在集合P中不能再次选择）。将顶点4加入集合P中，令book\[4\]=1。按照相同的方式更新dist数组。顶点4的所有出边<4,3>（dist\[3\] = dis\[4\]+e\[4\]\[3\]），<4,5>（dist\[5\] = dis\[4\]+e\[4\]\[5\]）和<4,6>（dist\[6\] = dis\[4\]+e\[4\]\[6\]）用同样的方法进行松弛。松弛完毕之后book数组和dist数组为：

（4）继续在剩余的顶点3、顶点5顶点和6中，选出离顶点1最近的顶点。选择3号顶点。此时，dis\[3\]的值已对3号顶点的所有出边（3->5）（dist\[5\] = dis\[3\]+e\[3\]\[5\]）进行松弛。松弛完毕之后dist数组为：

（5）继续在剩余的顶点5和顶点6，选出离顶点1最近的顶点，选择5号顶点。对5号顶点的所有出边（5->4）（dist\[4\] = dis\[5\]+e\[5\]\[4\]）进行松弛。松弛完毕之后dist数组为：

（6）最后选择顶点6加入集合P，令book\[6\]=1。由于6号顶点没有出边，因此不用进行松弛处理。最终得到的dist数组如下：

### 4.4 算法分析 ###

**复杂度：**迪杰斯特拉（Dijkstra）算法适用于权值为非负的图的单源最短路径，使用最小堆时间复杂度是O(VLogV)，用斐波那契堆的复杂度O(E+VlgV)。  
  **为什么不能有负权边：**Dijkstra算法当中将节点分为已求得最短路径的集合（记为P）和未确定最短路径的个集合（记为Q），归入P集合的节点的最短路径及其长度不再变更，如果边上的权值允许为负值，那么有可能出现当与P内某点（记为a）以负边相连的点（记为b）确定其最短路径时，它的最短路径长度加上这条负边的权值结果小于a原先确定的最短路径长度(意思是原先从a0---a已经确定一个最短路径，而此时的边权值为负，则此步骤中的边权计算结果必定小于已经确定了的路径长度)，但是a在Dijkstra算法下是无法更新的，由此便可能得不到正确的结果。

## 5 Bellman-Ford算法 ##

### 5.1 算法概述 ###

Bellman-Ford算法是从Dijkstra算法算法引申出来的，它可以解决带有负权边的最短路径问题。值得注意的是，Dijkstra算法和下面的Floyd算法是基于邻接矩阵的，而Bellman-Ford算法是基于邻接表，从边的角度考量的。用一句话概括就是：对所有的边进行n-1次松弛操作。如果图中存在最短路径（即不存在负权回路），那么最短路径所包含的边最多为n-1条，也就是不可能包含回路。因为如果存在正回路，该路径就不是最短的，而如果存在负回路，就压根就不存在所谓的最短路径。

### 5.2 算法流程 ###

（1）从源点到任意一点u的最短路径的长度，初始化数组dist\[u\]为0，其余dist\[i\]为无穷大。  
  （2）以下操作循环执行至多n-1次，n为顶点数：  
  对于每一条边edge(u,v)，如果dist\[u\] + weight(u,v) < dist\[v\]，则令dist\[v\] = dist\[u\] + weight(u,v)。若上述操作没有对dist进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；  
  （3）检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边edge(u,v)，如果存在dist\[u\] + weight(u,v) < dist\[v\]的边，则图中存在负环路，即是说该图无法求出单源最短路径。否则数组dist\[n\]中记录的就是源点s到各顶点的最短路径长度。

### 5.3 实例图解 ###

以图5.3.1所示的有向图为例，以顶点1为源点，采用Bellman-Ford算法计算最短路径。

![640?wx\_fmt=png][640_wx_fmt_png 2] 图5.3.1

（1）选取顶点1为源点，令dist\[1\]=1，dist\[2\]-dist\[6\]=INF。

（2）图中共有9条边，分别为<1，2>，<1，3>，<2，3>，<2，4>，<3，5>，<4，3>，<4，5>，<4，6>，<5，6>。对于每一条边执行松弛操作。此过程至多执行5次。

（3）第一次松弛操作：

> 对于边<1，2>，dist\[2\]=dist\[1\]+weight\[1,2\]=1 <INF。则dist\[2\]=1;
> 
> 对于边<1，3>，dist\[3\]=dist\[1\]+weight\[1,3\]=12<INF。则dist\[3\]=12;
> 
> 对于边<2，3>，dist\[3\]=dist\[2\]+weight\[2,3\]=10<12。则dist\[3\]=10;
> 
> 对于边<2，4>，dist\[4\]=dist\[2\]+weight\[2,4\]=4<INF。则dist\[4\]=4;
> 
> 对于边<3，5>，dist\[5\]=dist\[3\]+weight\[3,5\]=15<INF。则dist\[5\]=15;
> 
> 对于边<4，3>，dist\[3\]=dist\[4\]+weight\[4,3\]=8<10。则dist\[3\]=8;
> 
> 对于边<4，5>，dist\[5\]=dist\[4\]+weight\[4,5\]=17>15。则dist\[5\]=15;
> 
> 对于边<4，6>，dist\[6\]=dist\[4\]+weight\[4,6\]=19<INF。则dist\[6\]=19;
> 
> 对于边<5，6>，dist\[6\]=dist\[5\]+weight\[5,6\]=19<INF。则dist\[6\]=19;

得到的dist数组为：

![640?wx\_fmt=png][640_wx_fmt_png 3] img

（4）第二次松弛操作：

> 对于边<1，2>，dist\[2\]=dist\[1\]+weight\[1,2\]=1=1。则dist\[2\]=1;
> 
> 对于边<1，3>，dist\[3\]=dist\[1\]+weight\[1,3\]=12=12。则dist\[3\]=12;
> 
> 对于边<2，3>，dist\[3\]=dist\[2\]+weight\[2,3\]=10>8。则dist\[3\]=8;
> 
> 对于边<2，4>，dist\[4\]=dist\[2\]+weight\[2,4\]=4=4。则dist\[4\]=4;
> 
> 对于边<3，5>，dist\[5\]=dist\[3\]+weight\[3,5\]=13<15。则dist\[5\]=13;
> 
> 对于边<4，3>，dist\[3\]=dist\[4\]+weight\[4,3\]=8<10。则dist\[3\]=8;
> 
> 对于边<4，5>，dist\[5\]=dist\[4\]+weight\[4,5\]=17>13。则dist\[5\]=13;
> 
> 对于边<4，6>，dist\[6\]=dist\[4\]+weight\[4,6\]=19=19。则dist\[6\]=19;
> 
> 对于边<5，6>，dist\[6\]=dist\[5\]+weight\[5,6\]=17<19。则dist\[6\]=17;

得到的dist数组为：

![640?wx\_fmt=png][640_wx_fmt_png 4] img  
（5）第三次松弛操作：

得到的dist数组为：

![640?wx\_fmt=png][640_wx_fmt_png 5] img  
（6）第三次松弛操作没有对dist进行更新，说明最短路径已经查找完毕。最终结果为：  
![640?wx\_fmt=png][640_wx_fmt_png 6] img

### 5.4 算法分析 ###

Bellman-Ford算法初始化过程时间复杂度为O(V)，对边进行了V-1趟操作，每趟操作的运行时间为O(E)。整体的时间复杂度为O(V\*E)

## 6 SPFA算法 ##

### 6.1 算法概述 ###

SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法，它是Bellman-ford的队列优化。

### 6.2 算法流程 ###

（1）初始化：选取顶点u为源点，令dist\[u\]=0，其余赋值为INF。并将源点入队列。  
  （2）读取队列头的顶点，并将头顶点u出队列，将与u邻接的所有顶点v进行松弛，若v没有在队列中，则将邻接顶点v入队列。如果已经在队列中，则不再入队。  
  （3）队列为空时，单源最短路径查找完毕。

### 6.3 实例图解 ###

例如：图6.3.1所示有向图，以顶点1为源点，采用SPFA算法求解最短路径。

![640?wx\_fmt=png][640_wx_fmt_png 7] 图6.3.1

（1）执行初始化操作，并将顶点1入队列。

（2）顶点1出队列，邻接顶点有2、3。进行松弛操作：

dist\[2\] = dist\[1\]+weight\[1,2\] = 1;

dist\[3\] = dist\[1\]+weight\[1,3\] = 12;

更新dist数组，并将顶点2、3入队列。

（3）顶点2出队列，邻接顶点有3、4，进行松弛操作：

dist\[3\] = dist\[2\]+weight\[2,3\] = 10;

dist\[4\] = dist\[2\]+weight\[2,3\] = 4;

更新dist数组，并将顶点4入队列（顶点3已在队列中）。

（4）顶点3出队列，邻接顶点有5。进行松弛操作：

dist\[5\] = dist\[3\]+weight\[3,5\] = 17;

更新dist数组，并将顶点5入队列。

（5）顶点4出队列，邻接顶点有3、5、6。进行松弛操作：

dist\[3\] = dist\[4\]+weight\[4,3\] = 8;

dist\[5\] = dist\[4\]+weight\[4,5\] = 17;

dist\[6\] = dist\[4\]+weight\[4,6\] = 19;

更新dist数组，并将顶点3、6入队列。

（6）顶点5出队列，邻接顶点有6。进行松弛操作：

dist\[6\] = dist\[5\]+weight\[5,6\] = 19 = 19;

无需更新dist中数组值，同时无元素入队列。

（7）顶点3出队列，邻接顶点有5。进行松弛操作：

dist\[5\] = dist\[3\]+weight\[3,5\] = 13;

更新dist数组，并将顶点5入队列。

（8）顶点6出队列，无邻接顶点，无需松弛操作。无元素入队列。

（9）顶点5出队列，邻接顶点有6。进行松弛操作：dist\[6\] = dist\[5\]+weight\[5,6\] = 17;更新dist中数组值，顶点6入队列。

（10）顶点6出队列，无邻接顶点，无需松弛操作。无元素入队列。此时队列为空，求解过程结束。得到最终结果为：

## 6.4 算法分析 ##

SPFA算法是Bellman-Ford算法的一种优化。Bellman-Ford算法的复杂度是O(ev)，由于Bellman-Ford算法依次对每一条边进行松弛操作，重复n-1次后得到最短路径。SPFA算法中，如果一个顶点上没有被松弛过，那么下次就不会从这个点开始松弛。只将松弛过的点加入队列，减少了每个点的更新次数。

# 7 弗洛伊德（Floyd）算法 #

## 7.1 算法概述 ##

Floyd算法是一个经典的动态规划算法。其主要思想为：从任意顶点u到任意顶点v的最短路径不外乎2种可能，一是直接从u到v，二是从u经过若干个顶点k到v。所以，我们假设dist(u,v)为顶点u到顶点v的最短路径的距离，对于每一个顶点k，我们检查dist(u,k) + dist(k,v) < dist(u,v)是否成立，如果成立，证明从u到k再到v的路径比u直接到v的路径短，我们便设置dist(u,v) = dist(u,k) + dist(k,v)，这样一来，当我们遍历完所有顶点k，dist(u,v)中记录的便是u到v的最短路径的距离。

## 7.2 算法流程 ##

（1）从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 　　  
  （2）对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比己知的路径更短。如果是更新它。

### 7.3 实例图解 ###

例如：图7.3.1所示的有向图采用Floyd算法求解最短路径。选取顶点1为源点，顶点3为终点。

![640?wx\_fmt=png][640_wx_fmt_png 8] img  
  （1）选取单边路径为<1,3>，由于顶点1与顶点3距离为12。  
  （2）遍历剩余顶点2、4、5、6，寻找是否有可以选做中间站的顶点，使得顶点1到顶点3路径小于12。  
  （3）遍历完毕后，找到中间顶点2。选择顶点2位中间顶点，使得因此顶点1到顶点3最短路径为10。此时需要走的路径为（1,2），（2,3）。  
  （4）（1,2）边路径已经为最短路径，不存在中转顶点。遍历剩余顶点寻找（2,3）之间的中转顶点，发现通过顶点4可以使得1->3路径更短，路径长度为7。以此类推，逐逐步寻找最短路径。  
  例如：图7.3.1所示的有向图采用Floyd算法求解最短路径。选取顶点2为源点，顶点5为终点。  
  （1）顶点2与顶点5不邻接，因此距离为INF  
  （2）顶点2与顶点5可以通过顶点3中转，经过中转后距离为14。此时路径为2->3->5。  
  （3）顶点2到顶点3又可以通过顶点4中转，经过转后顶点2至顶点5距离为12。此时路径为2->4->3->5。

### 7.4 算法分析 ###

弗洛伊德（Floyd）算法的核心代码如下：

for(int i = 1; i <= n; i++)//枚举所有顶点，i代表顶点u
    
    {
          
    
        for(int j = 1; j <= n; j++)//枚举所有顶点，j代表顶点v
    
        {
          
    
            for(int k = 1; k <= n; k++)//查找是否有中间顶点w使得从u到w再到v比己知的路径更短
    
            {
          
    
                if(dist[j][k] > dist[j][i] + dist[i][k])
    
                {
        
    
                    dist[j][k] = dist[j][i] + dist[i][k];
    
                }
    
            }
    
        }
    
    }

可以看出Floyd算法是一种暴力破解的方式获取最短路径。Floyd算法的时间复杂度为O(n^3)，空间复杂度为O(n^2)。Floyd算法可以获得任意顶点对之间的最短路径。

## 8 结语 ##

最短路径问题是图论研究中的一个经典算法问题。因此针对图最短路径问题先后提出了许多算法。各类算法的应用场景不尽相同。Dijkstra算法和Bellman-Ford算法用于解决单源最短路径，而Floyd算法可以解决多源最短路径。  
  Dijkstra算法适用稠密图（邻接矩阵），因为稠密图问题与顶点关系密切。Bellman-Ford算法算法适用稀疏图（邻接表），因为稀疏图问题与边关系密切。 Floyd算法在稠密图（邻接矩阵）和稀疏图（邻接表）中都可以使用。

**推荐阅读**

[拜托，面试官别问我「布隆」了][Link 1]

[数据结构与算法： 三十张图弄懂「图的两种遍历方式」][Link 2]

[昨天，终于拿到了腾讯 offer][offer]

[几道和「二叉树」有关的算法面试题][Link 3]

[几道和散列（哈希）表有关的面试题][Link 4]

[一道看完答案你会觉得很沙雕的「动态规划算法题」][Link 5]

[几道和「堆栈、队列」有关的面试算法题][Link 6]

[链表算法面试问题？看我就够了！][Link 7]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

欢迎关注![640?wx\_fmt=png][640_wx_fmt_png 9]

[640_wx_fmt_jpeg]: /images/20220218/b56c0e586ca74182a4a050d7b8673607.png
[640_wx_fmt_png]: /images/20220218/2725b30cb7b446d787b18316ed48820e.png
[640_wx_fmt_png 1]: /images/20220218/f9755992331247148720b7e5533ba6fb.png
[640_wx_fmt_png 2]: /images/20220218/9df8365cd9524f71b9fef0f11e5ac76d.png
[640_wx_fmt_png 3]: /images/20220218/f2a02393167a4254abf6c70eaea92388.png
[640_wx_fmt_png 4]: /images/20220218/fa084f67af334a5f98dca01d46b5894b.png
[640_wx_fmt_png 5]: /images/20220218/21549d8ca74544bea7f80bd840f1f9c6.png
[640_wx_fmt_png 6]: /images/20220218/9f6abfd99add4ccf8599ac09161dd9e2.png
[640_wx_fmt_png 7]: /images/20220218/61b96c42870e41d788953e924c2c8d6f.png
[640_wx_fmt_png 8]: /images/20220218/f9bb428212634f82a0cfbf34858ec451.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485011&idx=1&sn=a3031a3d3ad033e44439d42d72753e16&chksm=fa0e69d2cd79e0c45b1eb017c65b60662890f67ec70ef44e92ef7f5cddfc313ea6ab353952f4&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485076&idx=1&sn=ba747d1efd4c009da83681a6bb4ff549&chksm=fa0e6915cd79e003249e9ee045d09a174b0e5aff2a6ecd807e10fd01bfbc1a37da688eb51637&scene=21#wechat_redirect
[offer]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485001&idx=1&sn=cdcebef70aaabcafa3403c2dd51bdfb7&chksm=fa0e69c8cd79e0de12ece3a9e48430099c429aff816cc3a9e40035192dc07a864864888d1078&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484985&idx=1&sn=93343d355abf36c77a361c9931cbe2d1&chksm=fa0e69b8cd79e0ae1e6b57665a456da5f421cc92fe6934337f1eb1e18c3fd6a3c1adc8ca88c2&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484977&idx=1&sn=f4a6148480555e3cca83231ac1df8d02&chksm=fa0e69b0cd79e0a686e31c547fc783eb9663d9fe19cc95ecd524e9f8f7e0d4a168945f8755e5&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484875&idx=1&sn=72cf66da1c970ba345e8b1ab3586c10d&chksm=fa0e6a4acd79e35c32c9201e99cc93a71d0f2a331319addf5303c76ac05738b312ab238a8304&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484846&idx=2&sn=e508da06e9f7a0b3d00db5415d7ce622&chksm=fa0e6a2fcd79e3397fe8083f9493ae639f47c9448ac2a0026026494d098c47ecc6e08f1f8e28&scene=21#wechat_redirect
[Link 7]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect
[640_wx_fmt_jpeg 1]: /images/20220218/35f8c14b15b44285be9c412bfcd57cb8.png
[640_wx_fmt_png 9]: /images/20220218/395ee68cb1f14f04ae47e6dd6063d756.png