“条条大路通罗马”，这是一句古老的谚语。

但在面对众多通往目的地的道路选择时，该如何决定走哪一条？一个显而易见的选择是最短的那条。常识也提醒我们应避开交通拥堵的路线，或那些耗时、耗钱较多的路径。

考虑到这些因素，当我们开始思考如何通过算法寻找到达目的地的最佳路径时，就需要一个清晰且灵活的模型，能够适应我们对“最佳”路径的不同偏好。

网络作为加权有向图

在这种情况下，道路网络通常被表示为一个加权有向图。网络中的每个节点用一个顶点表示，每条道路则建模为一条带有数值的边，这个数值称为该边的权重。

权重可以表示边两端之间的距离，也可以表示其他成本，例如穿越道路所需的时间，或与该道路相关的金钱成本。事实上，根据具体应用场景，边的权重甚至可以为负数。此外，所研究的网络也不限于道路网络。

我们使用一个 $n \times n$ 的二维数组来表示简单加权有向图的边权重，其中 $n$ 是顶点的数量。对于每条边 $(u,v)$，$weight[u][v]$ 表示其权重。

对角线元素设为 0，因为从一个顶点到自身没有代价。

$$weight[v][v] = 0 \qquad \text{对每个顶点 } v$$

如果从顶点 $u$ 到顶点 $v$ 没有边，则使用 $\infty$ 作为表示代价过大的虚拟值。

$$weights[u][v] = \infty \qquad \text{当 } (u,v) \text{ 不是边时}$$

例如，下图所示的有向图对应的权重矩阵如下：

最短路径

在加权有向图中，两个顶点之间的最短路径指的是总权重最小的路径（并非一定边数最少）。

路径的长度是路径中所有边权重之和。

我们来找出从 $v_1$ 到 $v_3$ 的最短路径。

在上述例子中，从 $v_1$ 到 $v_3$ 有三条（简单）路径。其中最短的一条是 $\langle v_1 , v_4, v_5, v_3 \rangle$，因为这条路径的长度为 3，而另外两条路径 $\langle v_1 , v_5, v_3 \rangle$ 与 $\langle v_1 , v_2, v_3 \rangle$ 虽然边数更少，但长度分别为 4 和 5。

从顶点 $u$ 到顶点 $v$ 的最短路径，是指所有 $u$ 到 $v$ 路径中长度（即总权重）最小的那一条。

如果所有边的权重都为 1（或图无权），那么最短路径就等价于边数最少的路径。

记号说明：我们用 $u-v$ 路径表示从顶点 $u$ 到顶点 $v$ 的路径。

在接下来的课程中，我们将介绍最短路径问题的不同类型：

最短路径问题的不同类型

• 单源最短路径问题：即从一个指定的源点出发，求出到图中所有其他顶点的最短路径。

  例如，在下图中若将顶点 $s$ 视为源点，则问题要求找出从 $s$ 到其余所有顶点的最短路径。

  ...

  从源点 s 到其他各顶点的最短路径，已用高亮显示

• 所有点对最短路径问题：即求出图中每一对顶点之间的最短路径。

  显然，可以通过对每个顶点作为源点分别求解单源最短路径问题，来得到所有点对的最短路径，但存在更高效的方法。

负权环

我们可以像定义路径权重一样定义环的权重：

一个环的权重是该环中所有边权重之和。

加权有向图可以包含负权重边，但如果某个环的权重总和为负数，就会对当前目标造成问题。

问题出现在：当可以从源点到达一个负权环上的某个顶点时，就可以在这个环上无限次循环，每次循环后累计经过的边权重不断减小。

多次经过同一顶点在技术上违反了“路径”的定义，即使我们放宽定义，将“最短路径”扩展为允许重复访问顶点的“最短步行”（walk），仍然无法定义“最短”——因为总权重可以无限减小，不存在下界。

因此，对于包含可从源点到达的负权环的有向图，寻找最短路径的问题被认为是未明确定义的。