穆罕默德-本-拉希-德阿勒马克图姆
图存储结构中，我们将从某一顶点到另一顶点总权值最小的路径称为最短路径。最短路径算法常用于解决以下几类问题：
在指定图结构中，找到某一顶点到另一个顶点总权值最小的路径；
在指定图结构中，找到某一顶点到其它各个顶点总权值最小的路径；
在指定图结构中，找到任意两个顶点之间总权值最小的路径；
根据实际场景的需要，最短路径算法既可以在无向加权图中寻找最短路径，如图 1 所示：
图 1 无向加权图
也可以在有向加权图中寻找最短路径：
图 2 有向加权图
举个例子，我们尝试分别在图 1 和图 2 所示的图结构中寻找从顶点 c 到顶点 a 的最短路径：
图 1 中，从顶点 c 到顶点 a 的路径有 3 条，分别是 c-a、c-b-a 和 c-b-d-a。这 3 条路径中，c-a 的总权值最小，因此 c-a 路径是顶点 c 到顶点 a 的最短路径；
图 2 中，从顶点 c 到顶点 a 的路径有 2 条，分别是 c-b-a 和 c-b-d-a，其中 c-b-a 的总权值最小，因此 c-b-a 是顶点 c 到顶点 a 的最短路径。
最短路径算法的用途很广泛，比如建立道路交通网、物流运输网络、计算机网络等。此外，任何帮我们规划出行线路的地图软件也都会用到最短路径算法。
最短路径算法的种类
所有的最短路径算法既适用于有向加权图，也适用于无向加权图。需要注意的是，有些最短路径算法要求所有路径的权值必须为非负数，而有些最短路径算法允许路径的权值为负数。
表 1 罗列了常见的几种最短路径算法以及它们的特点。
| 最短路径算法 | 描 述 |
|---|---|
| 贝尔曼福特算法（bellman-ford） | 寻找某个特定顶点到其它所有顶点的最短路径，该算法允许路径的权值为负数。 |
| 迪杰斯塔拉算法（dijkstra） | 寻找某个特定顶点到其它所有顶点的最短路径，该算法要求所有路径的权值为非负数。 |
| 弗洛伊德算法（floyd-warshall） | 寻找各个顶点之间的最短路径，允许非环路的路径权值为负数，该算法不仅适用于稀疏图，在稠密图（路径数量多的图）中寻找最短路径的效率也很高。 |
| 约翰逊算法（johnson） | 寻找各个顶点之间的最短路径，允许非环路的路径权值为负数，该算法更适用于稀疏图（路径数量少的 |
