图结构最短路径算法概览
一句话总结
Dijkstra 算法和 A* 算法是 图的 BFS 遍历 的拓展，可以处理不包含负权重的单源最短路径问题。
SPFA 算法（基于队列的 Bellman-Ford 算法）是 图的 BFS 遍历 的拓展，可以处理包含负权重的单源最短路径问题。
Floyd 算法是 动态规划 的应用，可以处理多源最短路径问题。
初学者不要觉得图论算法有多难，因为它们都是基于简单的算法思想扩展出来的。你把基本的二叉树层序遍历玩明白，自己都能发明出来这些算法，没啥了不起的。
考虑到目前处在基础知识章节，所以本文并不会详细讲解每种算法的完整代码，具体的代码实现会安排在之后的章节。
本文的重点在这些算法的关键原理、适用场景，以及这些高级算法和基础知识的联系，帮助初学者对图结构的最短路径算法有一个整体的认识。
最短路径问题概览
最短路径问题在生活中应用广泛，比方说计算最小成本、最短路径长度、最少时间等。
在算法中，我们一般把这类问题抽象成计算 加权图 中的最小路径权重。为了方便表述，在本文中「最短路径」和「最小路径权重和」是等价的。
最短路径问题大致可以分为「单源最短路径」和「多源最短路径」两类，下面会介绍几个经典的算法。
单源最短路径
所谓单源最短路径，就是让你计算从某个起点出发，到其他所有顶点的最短路径。
比方说一幅图中有 n 个节点，编号为 0, 1, 2, ..., n-1，让你计算从 2 号节点到其他节点的最短路径，这就是单源最短路径问题。
单源最短路径算法最终得到的输出应该是一个一维数组 distTo，distTo[i] 表示从起点到节点 i 的最短路径长度。
比较有代表性的单源最短路径算法有：
1、Dijkstra 算法，其本质是 BFS 算法 + 贪心思想，效率较高，但是不能处理带有负权重的图。
2、基于队列的 Bellman-Ford 算法，其本质也是 BFS 算法，可以处理带有负权重的图，但效率比 Dijkstra 算法低。
点对点最短路径
很多算法题中不需要我们计算起点到所有其他节点的最短路径，仅需要计算从起点 src 到某一个目标节点 dst 的最短路径。这类问题可以称为点对点最短路径问题。
一般来说，点对点最短路径问题可以视为单源最短路径问题的特例，你可以从 src 开始执行单源最短路径算法，当算出到达 dst 的最短路径时提前结束算法。
但是下面将介绍一种专门处理点对点问题的算法：A* 算法（A Star Algorithm）。
我经常讲，算法的本质是穷举，你想要提高穷举的效率，就得尽可能充分地利用信息。点对点最短路径问题（已知起点和终点）比单源最短路径问题（已知起点）多了终点信息，所以完全有可能利用这个信息来提高算法的效率。
比方说，如果我们知道终点在起点的右下方，那么我们有理由猜测：应该优先向右下方搜索，可能可以更快地到达终点。
A* 算法的关键就在这里：它能够充分利用已知信息，有方向性地进行搜索，更快地找到终点。我们称这类算法为启发式搜索算法（Heuristic Search Algorithm）。
但是请注意，这个猜测只是经验法则，并不一定总是正确。比方说右下方可能都是死路，偏偏就得经过左上角绕个大弯才能到达终点。
所以启发式算法需要合理设置启发函数（Heuristic Function），在经验法则和实际情况中找到平衡，确保在经验法则失效时，算法的效率也不会太差。
多源最短路径
所谓多源最短路径，就是让你计算任意两节点之间的最短路径。
比方说一幅图中有 n 个节点，编号为 0, 1, 2, ..., n-1，让你计算所有节点之间的最短路径，这就是多源最短路径问题。
多源最短路径算法最终得到的输出应该是一个二维数组 dist，dist[i][j] 表示从节点 i 到节点 j 的最短路径长度。
最有代表性的是 Floyd 算法，其本质是动态规划算法。
理论上，我们对所有节点都调用一次单源最短路径算法，就可以得到多源最短路径的解。
但具体实现时，要根据图结构的特点来选择。有些场景用 Floyd 这种多源最短路径算法效率更高，有些场景多次调用 Dijkstra 这种单源最短路径算法效率更高。后面讲到这些算法的复杂度时，你就能理解了。
负权重边的影响
在计算最短路径时，需要着重注意的是这幅图是否包含负权重边；一旦包含负权重边，一定要检查是否包含负权重环。
为啥负权重边会影响最短路径算法呢？因为负权重边会让问题变得复杂。举个最简单的例子就能直观地理解了：
比方说我们现在站在起点 s 上，相邻节点有 a 和 b，s->a 权重为 3，s->b 权重为 4。
如果这幅图不存在负权重边，那么根据上述信息，我就已经可以确定 s 到 a 的最短路径是 s->a，权重和为 3。因为你从 s->b 这条路径走出去，绕一圈到达 a 的路径权重和肯定是大于 4 的，不可能比 3 还小。
但如果这幅图存在负权重边，那可就不一定了。因为可能出现负权重边呀，比方说 b->a 的权重为 -10，那么从 s->b->a 的路径权重和为 -6，比 s->a 的路径权重和 3 还小。
想让 Dijkstra 这类包含贪心思想的算法成立，需要一个前提：它假设随着经过的边的数量增加，路径权重和一定也会增加。但负权重边的出现打破了这一假设，导致算法失效。
如果图中存在负权重环，最短路径问题就没有意义了。比方说 s 到 a 的路径上存在负权重环，那么你可以在这个负权重环上无限转圈，使得路径权重和无限减小下去。
常见最短路径算法中，Dijkstra 算法和 A* 算法不能处理含有负权重边的图，Floyd 算法和 Bellman-Ford 算法可以处理负权重边，Bellman-Ford 算法常用来检测负权重环。
下面，我们介绍这些算法的核心原理。