阅读:0       作者:解学武

最短路径是什么

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

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

举个简单的例子:

图 1 有向网

图 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,只要输入目的地,导航会自动帮我们规划一条距离最短的路线,这是最短路径在实际生活中的典型应用之一。

最短路径问题的解决方案

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

解决最短路径问题,最常用的方案有两种,分别叫做「迪杰斯特拉算法」和「弗洛伊德算法」:
  • 迪杰斯特拉算法:查找某个顶点到其它顶点之间的最短路径;
  • 弗洛伊德算法:查找任意两个顶点之间的最短路径。

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