笔记汇总

$spfa$ 是一个以 迭代 为核心思想的图论算法。

主要通过 松弛 的操作来维护图上携带的信息。

$dist[u] = min(dist[u], dist[v] + w[v, u])$

这个式子就是广为人知的 三角不等式 中求最短路的一种，将 两短边 和 一长边 比较，保留较小值。

为什么以上的操作是正确的，可以先看一下迭代的释义。

迭代： 不断交换替代，以逼近所需目标。

也就是说，我们通过运用 三角不等式 比较图上的边来逼近求出最短路的目的。

如此，我们可以再进行一定的扩展。

如果，改变计算 一个集合内 数值的步骤，不影响最终结果的情况下，都可以运用 $spfa$ 计算极值。

这句话蕴含了两个重要的性质：

一、可以处理满足交换律的信息

二、可以处理负权值

三、可以计算最大值或最小值

四、可以计算 $max$ 或 $min$ 覆盖

第一个性质较显然不讲。

第二条性质 证明如下：

例如 $a - b = -b + a$，即减法操作(负权)满足 交换律，得证。

第三条性质 证明如下：

因为 $spfa$ 实现的核心是 迭代，则拿 两条边 和 第三条 的比较并没有什么特殊的要求。

$a + b > c$ 、 $a + b < c$ 或 $a + b = c$ 皆可。

第四条性质 证明如下：

满足交换律，正确。