图结构最短路径算法概览
初学者不要觉得图论算法有多难，因为它们都是基于简单的算法思想扩展出来的。你把基本的二叉树层序遍历玩明白，自己都能发明出来这些算法，没啥了不起的。
考虑到目前处在基础知识章节，所以本文并不会详细讲解每种算法的完整代码，具体的代码实现会安排在之后的章节。
本文的重点在这些算法的关键原理、适用场景，以及这些高级算法和基础知识的联系，帮助初学者对图结构的最短路径算法有一个整体的认识。
最短路径问题概览
最短路径问题在生活中应用广泛，比方说计算最小成本、最短路径长度、最少时间等。
在算法中，我们一般把这类问题抽象成计算 加权图 中的最小路径权重。为了方便表述，在本文中「最短路径」和「最小路径权重和」是等价的。
最短路径问题大致可以分为「单源最短路径」和「多源最短路径」两类，下面会介绍几个经典的算法。
单源最短路径
所谓单源最短路径，就是让你计算从某个起点出发，到其他所有顶点的最短路径。
比方说一幅图中有 n 个节点，编号为 0, 1, 2, ..., n-1，让你计算从 2 号节点到其他节点的最短路径，这就是单源最短路径问题。
单源最短路径算法最终得到的输出应该是一个一维数组 distTo，distTo[i] 表示从起点到节点 i 的最短路径长度。
很多算法题中不需要我们计算起点到所有其他节点的最短路径，仅需要计算从一个起点 src 到某一个目标节点 dst 的最短路径。这类问题可以视为单源最短路径问题的特例。
比较有代表性的单源最短路径算法有：
1、Dijkstra 算法，其本质是 BFS 算法 + 贪心思想，效率较高，但是不能处理带有负权重的图。
2、基于队列的 Bellman-Ford 算法，其本质也是 BFS 算法，可以处理带有负权重的图，但效率比 Dijkstra 算法低。
多源最短路径
所谓多源最短路径，就是让你计算任意两顶点之间的最短路径。
比方说一幅图中有 n 个节点，编号为 0, 1, 2, ..., n-1，让你计算所有顶点之间的最短路径，这就是多源最短路径问题。
多源最短路径算法最终得到的输出应该是一个二维数组 dist，dist[i][j] 表示从节点 i 到节点 j 的最短路径长度。
最有代表性的是 Floyd 算法，其本质是动态规划算法。
理论上，我们对所有节点都调用一次单源最短路径算法，就可以得到多源最短路径的解。
但具体实现时，要根据图结构的特点来选择。有些场景用 Floyd 这种多源最短路径算法效率更高，有些场景多次调用 Dijkstra 这种单源最短路径算法效率更高。后面讲到这些算法的复杂度时，你就能理解了。
负权重边的影响
在计算最短路径时，需要着重注意的是这幅图是否包含负权重边。
比方说求解单源最短路径的算法，Dijkstra 算法不能处理含有负权重边的图，Bellman-Ford 算法可以处理负权重边，但效率会比 Dijkstra 算法差一些；求解多源最短路径的 Floyd 算法可以处理负权重边。
为啥负权重边会影响最短路径算法呢？因为负权重边会让问题变得复杂。举个最简单的例子就能直观地理解了：
比方说我们现在站在起点 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 这类包含贪心思想的算法成立，需要一个前提：它假设随着经过的边的数量增加，路径权重和一定也会增加。但负权重边的出现打破了这一假设，导致算法失效。
对应的，如果无法运用贪心思想，那么算法的效率必然会降低。
下面，我们介绍几种经典的单源最短路径算法的核心原理。