单源最短路径问题 Dijkstra算法 之 小木乃伊到我家

木乃伊到我家"/>

单源最短路径问题 Dijkstra算法 之 小木乃伊到我家

如图，圈代表点，线代表边即两点之间距离。以我们的超强大脑不费摧毁之力就可以看出 节点1和节点4之间的最短距离为3；但是点越多，边越多，图就会非常复杂，这时候我们就需要想一个算法程式来解决这种问题（最短路径问题）。

给定一个带权图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源（起点）。现在要计算从源到其他所有各顶点的最短路径长度。而这个长度就是指最短路径这条路上各边权值之和。这个问题通常称为单源最短路径问题。

这个问题在生活中很常见，可以应用到生活中多种场合，例如：优化管道、路由表、快递服务、通信网站等。

而解决最短路径问题的算法有诸多：Dijkstra、Bellman-Ford、SPFA、Floyd、A*算法。每一种算法都有其巧妙之处，都值得我们去学习：

Dijkstra：适用于权值为非负的带权有向或无向图的单源最短路径，用邻接表，不优化，复杂度O(V 2 +E)

Bellman-Ford：适用于含负权边的带权有向图（即要求不能包含权值总和为负值回路(负权值回路)）的单源最短路径，并且能够检测负环并输出负环，复杂度O(VE)