Dijkstra 算法的延伸

我们知道 Dijkstra 算法是一个高效的单源最短路径（SSSP）算法，本文将不再赘述他的细节。但同时，Dijkstra 也是一个动态规划算法。Dijkstra 算法的正确性源自无负边权图的若干性质。如果一个问题本身也满足这些性质，那么即使它不是一个图论最短路径问题，也可以使用 Dijkstra 算法解决。那么，这些性质是什么呢？

SSSP 问题的延伸

我们可以从更加抽象的层次描述 SSSP 问题。设想有一个函数 $W: [n] \times [n] \times \mathbb{R}^+ \mapsto \bar{\mathbb{R}}$，对 $\forall g, g_1, g_2 \in \mathbb{R}^+, g_1 < g_2, i, j \in [n], i \neq j$ 满足以下性质

$$\begin{align} W(i, i, g) &= 0, \\ W(i, j, g) &\geq 0, \\ W(i, j, g_1) - W(i, j, g_2) &\leq g_2 - g_1 \label{eq:bound} \end{align}$$

$W$ 可以看成一个广义的权值函数，带有一个额外的自变量 $g$。在实际问题中 $g$ 可以是“已走过的距离”等额外参数。而 $\eqref{eq:bound}$ 约束了 $W$ 随着 $g$ 最多只能以线性速度衰减，这对后面的证明是十分必要的。注意 $W$ 的值域是扩充实数域，为了保持一致性，我们额外规定 $\infty - \infty = 0$。

另一方面，我们记 $[n]$ 中元素构成的子序列的集合为 $\mathcal{U}$

$$\mathcal{U} = \{(a_1, a_2, \ldots, a_k)|k \in \mathbb{N}, a_1, \ldots, a_k \in [n]\}$$

$\mathcal{U}$ 中元素我们用加粗小写字母 $\mathbf{a}, \mathbf{b}$ 表示，$|\mathbf{a}|$ 为 $\mathbf{a}$ 的长度，$a_i$ 为 $\mathbf{a}$ 的第 $i$ 个元素，$\mathbf{a}_{q}$ （如 $\mathbf{a}_{\leq k}$）为 $\mathbf{a}$ 中下标满足条件 $q$ 的元素构成的子序列。同时，我们还定义 $||$ 为序列拼接运算符。有了以上准备，现在我们定义路径长度函数 $L: \mathcal{U} \mapsto \bar{\mathbb{R}}$：

$$ \begin{align} L(\mathbf{a}) &= W(1, a_1, 0), &\text{if } |\mathbf{a}| = 1; \\ L(\mathbf{a}) &= L(\mathbf{a}_{\leq k-1}) + W(a_{k-1}, a_k, L(\mathbf{a}_{\leq k-1})), &\text{if } |\mathbf{a}| = k \geq 2. \end{align} $$

现在我们要求解另一个函数 $D: [n] \mapsto \mathbb{R}$，其定义如下

$$ \begin{align} D(u) = \min_{\mathbf{a} \in \mathcal{U}, |\mathbf{a}| \leq n} L(\mathbf{a}||u) \label{eq:D} \end{align} $$

上述这个问题可以用 Dijkstra 算法求解。在 SSSP 中，$W(i, j, g)$ 即为 $i$ 到 $j$ 的边权，$W(i, j, g)$ 是关于 $g$ 的常函数，$D(i)$ 则是 $i$ 到源点的最短路径。

延伸问题的求解

和 Dijkstra 算法类似，我们维护一个试探性数组 $p: [n] \in \mathbb{R}$。初始时，$p(i) \geq D(i), \forall i$。同时我们维护一个“已求解”的集合 $S$，记其补集 $T = [n] - S$。我们将经过 $n$ 次迭代，逐渐将 $S$ 填满。而在每次迭代开始前，我们会通过某种“更新”机制使 $p$ 满足如下条件：

$$ \begin{align} p(i) &= D(i), &\forall i \in S; \\ p(i) &= \min_{j \in S} \left(D(j) + W(j, i, D(j)\right)), &\forall i \in [n].\label{eq:ST} \end{align} $$

在每次迭代中，我们从 $T$ 中取出

$$\begin{align}u = \arg\min_{i \in T}d(i)\label{eq:u}\end{align}$$

，并认为 $i$ 已经“求解完成”，将其加入 $S$。为什么可以这么做呢？我们可以用以上的条件证明其正确性。

利用反证法，如果说 $u$ “还未求解完成”，也就是此时 $p(u) > D(u)$。由 $\eqref{eq:D}$ 中 $\mathbf{a}$ 的取值集合有限可知，$\exists \mathbf{a}, |\mathbf{a}|=k$，使得 $D(u) = L(\mathbf{a}||u)$。我们讨论两种情况：

第一种，如果 $\mathbf{a} \subset S$，

$$ \begin{align*} D(u) &< p(u) & 利用 \eqref{eq:ST}\\ &\leq D(a_k) + W(a_k, u, D(a_k)) & 利用 D(a_k) \leq L(\mathbf{a}) 以及 \eqref{eq:bound}\\ &\leq D(a_k) + W(a_k, u, L(\mathbf{a})) + L(\mathbf{a}) - D(a_k) \\ &= W(a_k, u, L(\mathbf{a})) + L(\mathbf{a}) & 利用 D(u) = L(\mathbf{a}||u)\\ &= D(u) \end{align*} $$

矛盾！

第二种，如果诸 $\mathbf{a}$ 中有不属于 $S$ 的元素，假设 $a_j \in T$ 是其中下标最小者。则有

$$ \begin{align*} p(u) &> D(u) \\ &= L(\mathbf{a}_{<j}||a_j||\mathbf{a}_{>j}||u) \\ &\geq L(\mathbf{a}_{<j}||a_j) \\ &= L(\mathbf{a}_{<j}) + W(a_{j-1}, a_j, L(\mathbf{a}_{<j})) &利用 D(a_{j-1}) < L(\mathbf{a}_{<j})\\ &= L(\mathbf{a}_{<j}) + W(a_{j-1}, a_j, D(a_{j-1})) + D(a_{j-1}) - L(\mathbf{a}_{<j}) \\ &= W(a_{j-1}, a_j, D(a_{j-1})) + D(a_{j-1}) & 利用 a_{j-1} \in S 及 \eqref{eq:ST}\\ &\geq p(a_j) \end{align*} $$

这与 $u$ 的选取矛盾！故综上，如此选出的 $u$ 一定是“已经求解完成的”。

选出了 $u$ 后，我们需要以 $u$ 为基点，更新 $Y$ 中其他元素的 $d$ 值。具体而言，对于 $\forall j \in T$，我们作如下更新

$$p(j) \gets \min(p(j), D(u) + W(u, j, D(u)))$$

我们可以证明这样的更新方式符合 $\eqref{eq:ST}$ 的要求

$$ \begin{align*} &\min\left\{p(j), D(u) + W(u, j, D(u))\right\} \\ = &\min\left\{\min_{w \in S}\{D(w)+W(w, j, D(w))\}, D(u, W(u, j, D(u)))\right\} \\ = &\min_{w \in S \cup \{u\}}\{D(w)+W(w, j, D(w))\} \end{align*} $$

由此可知，Dijkstra 的改进算法可以解决这个延伸问题。

应用

前面说过，SSSP 是延伸问题的一个特殊情况。此外，本文的算法还可以用来解决一些特殊的最短路径问题。比如在 LeetCode 2577. Minimum Time to Visit a Cell In a Grid 中，图的边权不是一个常数，而是随着当前已走的距离（或时间）增加而减少，而且减少的幅度不超过线性速度。可以验证，这道题的条件满足上面的约束，因此也可以用 Dijkstra 算法来解决。

作者：hsfzxjy
链接：
许可：CC BY-NC-ND 4.0.
著作权归作者所有。本文不允许被用作商业用途，非商业转载请注明出处。