算法之「迪杰斯特拉（Dijkstra）算法」

最短路径

生活中，我们常常会面临着对路径的最优选择问题，可能是路程最短，也可能是时间最短，这个的最短路径就类似路程最短的选择。

比如在上海，乘地铁去某个地方，上海的地铁路线很多，从地图上看上去就是一个网。去某个地方就会有多条路线的选择，我们一般就会选最短那条路线。当然，在现实生活中，还会考虑时间、换乘等因素，这里只是举个例子说什么是最短路径。

地铁换乘貌似一眼就可以看出来那条路线是最优的路线。但是在一些复杂的情况下，人眼就很难确定最优路线来，比如送外卖、自驾车等。人眼就很难做出最优选择，因为路况等因素，根本没法判断。这时就需要用算法来选择最佳路线了。这也是这篇文章的主角：迪杰斯特拉（Dijkstra）算法。

迪杰斯特拉算法

迪杰斯特拉（Dijkstra，又译戴克斯特拉）算法由荷兰计算机科学家艾兹赫尔·迪杰斯特拉在1956年提出。使用了广度优先搜索解决带权有向图的单源最短路径问题。通过一个顶点作为源节点然后找到该顶点到图中所有其它节点的最短路径，产生一个最短路径树。

迪杰斯特拉算法步骤

1.标记所选的初始顶点，当前距离为 0，其余顶点设为无穷大。
2.将具有最小当前距离的非访问顶点设置为当前顶点 C。
3.对于当前顶点 C 的每个邻居顶点 N：将当前距离 C 与连接 C—N 的边缘的权重相加。 如果它小于顶点 N 的当前距离，则将其设置为 N 的新当前距离。
4.将当前顶点 C 标记为已访问。
5.如果有非访问顶点，重复步骤2，直到所有顶点均访问。

迪杰斯特拉算法时间复杂度

假如我们有 V 表示图中的顶点个数，E 表示图中的边个数。

如果用一个链表或者数组来存储所有顶点的集合，要找到最短路径算法所需的运行时间是 。

如果用邻接表 + 二叉堆来用作优先队列来查找最小的顶点，那么算法所需的时间为 。

如果用邻接表 + 斐波纳契堆能稍微提高一些性能，让算法运行时间达到 。

迪杰斯特拉算法示例

Dijkstra的算法是用来计算一个顶点（起始点）与图中每个其他顶点之间的最短路径。

image

搜索顶点 C 和图中其他顶点之间的最短路径。

image

首先我们需要初始化数据，选择顶点 C 为初始顶点，当前距离为 0，对于其余顶点，由于我们不知道最小距离，因此它开始为无穷大。

image

现在与 C 相邻的顶点为 A、B、D，因为没有特定的顺序，我们选择从 A 开始。由于 C 到 A 的权值为 1，当前顶点的最小距离加 C—A 的权值小于默认的无穷大，所以 C—A 的最小距离为 0+1=1。

image

由于 C 到 B 的权值为 7，当前顶点的最小距离加 C—B 的权值小于默认的无穷大，所以 C—B 的最小距离为 0+7=7。

image
由于 C 到 D 的权值为 2，当前顶点的最小距离加 C—D 的权值小于默认的无穷大，所以 C—D 的最小距离为 0+2=2。
此时 C—A 的最短距离为 1；
C—B 的最短距离为 7；
C—D 的最短距离为 2。 image
选取下一个当前顶点为 A，由于 A 到 B 的权值为 3，当前顶点的最小距离加 A—B 的权值小于 7，所以 C—B 的最小距离为 1+3=4。
当前的最短路径分别为 C—A、C—A—B、C—D。 image
选取下一个当前顶点为 D，由于 D 到 E 的权值为 7，当前顶点的最小距离加 D—E 的权值小于无限大，所以 C—E 的最小距离为 2+7=9。
此时 D—B 的权值为 5，C—B 的最小距离为 2+5=7，大于当前的最小距离，因此不用更新 C—B 的距离。
当前的最短路径分别为 C—A、C—A—B、C—D、C—D—E。 image

选取下一个当前顶点为 B，由于 B 到 E 的权值为 1，当前顶点的最小距离加 B—E 的权值小于 9，所以 C—E 的最小距离为 4+1=5。现在更新C—E 的最短距离为 5，所有顶点都以标记完成。

最后，最短距离分别为 C—A=1，C—B=4，C—D=2，C—E=5。
最短路径分别为 C—A、C—A—B、C—D、C—A—B—E。

总结

迪杰斯特拉（Dijkstra）算法使用了广度优先搜索解决带权有向图的单源最短路径问题。通过一个顶点作为源节点然后找到该顶点到图中所有其它顶点的最短路径。

用一个链表或者数组来做存储的数据结构时，时间复杂度为 。

但通过对存储结构的优化，用二叉堆或者斐波纳契堆来存储时，效率上有一定的提升。

PS:
清山绿水始于尘，博学多识贵于勤。
我有酒，你有故事吗？
微信公众号：「清尘闲聊」。
欢迎一起谈天说地，聊代码。