图详解第四篇：单源最短路径--Dijkstra算法

1. 最短路径问题

最短路径问题：

从带权有向图（求最短路径通常是有向图）G中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。

那下面我们就要来学习几个求最短路径的算法

2. 单源最短路径–Dijkstra算法

这篇文章我们先来学习第一个求单源最短路径的算法——迪杰斯特拉算法(Dijkstra)，是由荷兰计算机科学家狄克斯特拉于1959年提出的，然后后面我们还会学到求多源最短路径的算法。

所以这里先给大家介绍一下什么是单源最短路径，什么是多源最短路径：

单源最短路径指的是从一个源节点出发，计算到其他所有节点的最短路径。也就是说，在单源最短路径问题中，只需要确定一个起点，然后计算该起点到图中所有其他节点的最短距离。
多源最短路径则是在图中计算任意两个节点之间的最短路径。换言之，需要求解所有可能的起点和终点之间的最短路径。

那下面我们就来学习一下第一个求单源最短路径的算法——Dijkstra算法

算法思想

首先我们可以先从概念上了解一下Dijkstra算法的思想：

单源最短路径问题：给定一个图G = ( V ， E ) ，求源结点s ∈ V 到图中每个结点v ∈ V的最短路径。Dijkstra算法就适用于解决带权重的有向图上的单源最短路径问题，同时算法要求图中所有边的权重非负。一般在求解最短路径的时候都是已知一个起点和一个终点，所以使用Dijkstra算法求解过后也就得到了所需起点到终点的最短路径。
针对一个带权有向图G，将所有结点分为两组S和Q，S是已经确定最短路径的结点集合，在初始时为空（初始时就可以将源节点s放入，毕竟源节点到自己的代价是0），Q 为其余未确定最短路径的结点集合，每次从Q 中找出一个从起点到该结点代价最小的结点u ，将u 从Q 中移出，并放入S 中，对u 的每一个相邻结点v （且v不在S中）进行松弛操作。松弛即对每一个相邻结点v ，判断源节点s到结点u 的代价与u 到v 的代价之和是否比原来s 到v 的代价更小，若代价比原来小则要将s 到v 的代价更新为s 到u 与u 到v 的代价之和，否则维持原样。如此一直循环直至集合Q 为空，即所有节点都已经查找过一遍并确定了最短路径，至于一些起点到达不了的结点在算法循环后其代价仍为初始设定的值，不发生变化。
Dijkstra算法每次都是选择V-S中最小的路径节点来进行更新，并加入S中，所以该算法使用的是贪心策略。

Dijkstra算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路径的最短路径，这个我们后面也会给大家演示。

图解

那只看上面的概念的话，大家可能还不是特别理解，那下面我们来画图带大家分析一下

首先，我们可以先来看一下算法导论上给出的图解：

大家可以自己先看一下

然后，我来带大家走一遍这个过程：

其实就按照上面的思想一步步走就行了。
按照上面说的，将所有结点分为两组S和Q，S是已经确定最短路径的结点集合，Q 为其余未确定最短路径的结点集合。
那起始的时候，可以认为S是空的，所有结点都在Q里面。
然后这里选择的起点是s

每次从Q 中找出一个从起点到该结点代价最小的结点u，那第一次这个结点u就是s，可以认为s到s的距离是0（图中每个结点里面的值就表示当前从起点到自己的最短路径，还没更新的路径用∞标识），那把s结点放到S集合里面，Q中删去s；
然后对s 的每一个相邻结点v 进行松弛操作（其实去更新起点到它相邻点的距离），s到它相邻的两个结点距离s-t为10，s-y为5，都比原来从起点到它们的距离小，所以更新

然后再从Q里面找一个到起点路径最短的点，那这次找到的是y（此时s-y为5是最小的），把y从Q中移除，放入S里面；
然后对y进行松弛操作

y相邻的几个顶点到y的距离+y到起点s的距离都比之前起点到它们的距离短，所以都更新
接着继续从Q中选一个到起点距离最短的是z，z从Q中移出，放入S；
接着对x进行松弛操作，更新相应的距离

接着继续从Q中选一个到起点距离最短的是t，t从Q中移出，放入S；
接着对t进行松弛操作，更新相应的距离

再接着继续从Q中选一个到起点距离最短的是x，x从Q中移出，放入S；
接着再对x进行松弛操作

至此，集合Q 为空（起始Q是满的，所以n个结点的话，其实就选了n次去更新），即所有节点都已经查找过一遍并确定了最短路径
算法执行结束！

如何存储路径及其权值

相信算法现在大家已经理解了，但是还有一些问题需要我们解决：

既然我们是要求最短路径，那肯定得把相关的信息存储起来啊，上面图中直接把每个顶点对应最短路径的权值直接写到了结点里面，而且每条路径是怎么走的，经过了哪些顶点，我们也很容易看出来。

可是后面我们要写代码，那在写代码的时候我们如何把这些信息也存储起来呢？

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/444357