SPFA在随机图下的时间复杂度

· · 算法·理论

关于 SPFA

他ODT了

很显然，SPFA 在出题人刻意卡的情况下，最坏时间复杂度会到达 O(nm) ，但疑问的是，为何在绝大多数的图内 SPFA 就可以跑得巨快乃至于超越 dijkstra ,于是就有了这篇文章。

前置芝士

其作用为描述连续型随机变量在某个特定值附近的概率密度(并非概率本身，需要积分回去才为概率)。

那么对于随机变量 X， 其 PDF f_X(x) 满足:

\mathbb{P}(a \le X \le b) = \int_{a}^{b}{f_X(x)} dx

此时有一个关键性质 \int_{-\infty}^{\infty}{f_X(x)} dx = 1

比如正态分布的 PDF 为:

f(x) = \frac{1}{\sqrt{2\pi}\sigma} \exp\left(-\frac{(x - \mu)^2}{2\sigma^2}\right)

其中 \mu 为均值， \sigma 为标准差。

注 : \exp(x) = e^x

起作用为描述随机变量 X 小于等于某个值 x 的累计概率。

那么对于随机变量 X ,其 CDF 为

F_X(x) = \mathbb{P}(X \le x) = \int_{-\infty}^{x}f_X(t) dt

其关键性质有两个

  2. 当 x → \infty 时， F_X(x) → 1 ; 当 x → -\infty 时， F_X(x) → 0 。

比如正态分布的 CDF 为:

\Phi \left(\frac{x - \mu}{\sigma}\right)

其中 \Phi 是标准正态分布( \mu = 0, \sigma = 1 ) 。

(前置芝士结束了)

正文

我们设图 G = (V,E) 为随机图， 边权 w(u, v) 为独立随机变量

设 d_u 为节点 u 的当前最短路径的值， d_v 为节点 v 的当前最短路径值 (就是 SPFA 松弛条件中的起点和终点)

那么对于边 (u, v), 能够松弛的条件为

d_u + w(u,v) < d_v

此时则会松弛，即更新路径最小值

然后设每个节点 v 的入队次数为 X_v 。 若每次松弛成功的概率为 p, 则 X_v 的期望满足递推关系 E[X_v] = 1 + \Sigma_{(u,v)\epsilon E}p \cdot E[X_u]

那么问题就变成了对松弛成功概率 p 的分析

设成功松弛的概率为 p , 同时设 z = d_v - d_u。

所以成功松弛的概率为：

p = \mathbb{P}(w(u, v) < z)

其期望概率为:

\mathbb{E}[p] = \mathbb{E}_{z}\left[\mathbb{P}(w(u,v) < z)\right]

又因为 w(u,v) 与 z 互相独立，期望式子可展开为:

\mathbb{E}[p] = \int_{-\infty}^{\infty} \mathbb{P}(w(u,v) < z) \cdot f_z(z) dz 此时我们令边权 $w(u,v)∼\mathcal{N}(μ,\sigma^2)$ ,以及又因为 $d_u$ 和 $d_v$ 在随机图中分布近似独立，所以$z$ 符合正态分布，因此令 $z ∼ \mathcal{N}(\mu_z, \sigma_z^2)$ ( $\mu$ 表示均值， $\sigma^2$ 表示方差)。 此时我们可以求出关于 $w(u, v)$ 的累计分布函数即 CDF : $$ \mathbb{P}(w(u,v) < z) = \Phi\left(\frac{z - \mu}{\sigma}\right)$$ 同时也可求出 $f_z(z)$: $$ f_z(z) = \frac{1}{\sqrt{2\pi}\sigma_z} \exp\left(-\frac{(z - \mu_z)^2}{2\sigma_z^2}\right)$$ 此时将二者带入期望公式得到: $$\mathbb{E}[p] = \int_{-\infty}^{\infty} \Phi\left(\frac{z - \mu}{\sigma}\right) \cdot \frac{1}{\sqrt{2\pi}\sigma_z} \exp\left(-\frac{(z - \mu_z)^2}{2\sigma_z^2}\right) \, dz$$ 利用正态分布的线性组合性质~~使用科技~~将式子化简得到: $$\mathbb{E}[p] = \Phi\left(\frac{\mu_z - \mu}{\sqrt{\sigma^2 + \sigma_z^2}}\right)$$ 此时分析式子，在随机图中，$\mu_z$ 与 $\mu$ 同阶，同时由于图的稀疏性且每个边权独立且随机，$\sigma_z^2$ 与 $\sigma^2$ 同阶，因此原式为一个常数，使得 $\Phi(\cdot)$ 的值落在一个固定的常数区间，从而 $\mathbb{E}[p] = O(1)$, 这表明在 SPFA 中任意边成功松弛的概率期望值为常数，所以 SPFA 在随机图中时间复杂度为 $O(m)$。 ~~如果想写成 $O(km)$ 也可以， 反正带一个小常数~~