作者：解学武

在图结构中，一个顶点到另一个顶点的路径可能有多条，最短路径指的就是顶点之间“最短”的路径。

在不同的场景中，路径“最短”的含义也有所差异，比如途径顶点数量最少、总权值最小等。提到最短路径，往往指的是总权值最小的路径，所以常常在网结构（带权的图）中讨论最短路径问题，包括有向网和无向网。

举个简单的例子：
图 1 是一张有向网，其中从 V0 到 V5 的路径有多条，包括：

V0 -> V5，总权值为 100
V0 -> V4 -> V5，总权值为 30+60 = 90
V0 -> V4 -> V3 -> V5，总权值为 30+20+10 = 60
V0 -> V2 -> V3 -> V5，总权值为 10+50+10 = 70

通过比较这些路径的总权值，最终可以找到一条从 V0 到 V5 的最短路径。

现如今，大家出行再也不用担心找不到路了，车上有车载导航，手机上也可以安装各种导航 App，只要输入目的地，导航会自动帮我们规划一条距离最短的路线，这是最短路径在实际生活中的典型应用之一。

最短路径问题的解决方案

在指定的一张网中查找最短路径，该如何编码实现呢？

解决最短路径问题，最常用的方案有两种，分别叫做「迪杰斯特拉算法」和「弗洛伊德算法」：

• 迪杰斯特拉算法：查找某个顶点到其它顶点之间的最短路径；
• 弗洛伊德算法：查找任意两个顶点之间的最短路径。

关于这两种算法，接下来我会用两篇文章分别讲解它们。