浅谈差分约束系统与SPFA算法

鉴于今天做到了差分约束的题目,那么也顺便简单总结一下差分约束的基本求解思路,以及 $SPFA$ 算法的两个优化与如何通过 $SPFA$ 求最长路。

差分约束系统

一般来说,对于一类“两个未知数的差小于等于(或大于等于)某个常数” $(x_i - x_j \le c)$ 不等式组的求解,便是差分约束系统。差分约束系统的美妙之处在于可以将其转为图论,通过求解单源最短路来判断原不等式组是否有解甚至求得最大或最小解。

首先,显然对于此类不等式组,要么无解,要么有无数解。因为假设存在一组解为 ${x_1, x_2, …, x_n}$,那么对于任意一个常数 $k$,${x_1 + k, x_2 + k, …, x_n + k}$ 也必是一组解,因为他们的差值是不变的,所以不等式组依然成立。

接下来考虑单源最短路图,对于某点 $v$ 与其邻接点 $u$,显然 $dist[v] \le dist[u] + cost_{u->v}$,也即 $dist[v] - dist[u] \le cost_{u->v}$,正好满足“两个未知数的差小于等于某个常数”。因此,我们将待求解不等式组中的未知数看成图上的顶点,对于每个不等式 $x_i - x_j \le c$,转化成图中顶点 $i$ 向 $j$ 建边,边权为 $c$。

然后直接在建成的图上跑单源最短路就可以了。如果存在负环则无解,否则 ${dist[i]}$ 便是其中一组解,至于以哪个点作为源点都是可以的。相当于以哪个点作为源点就是将该点赋值为 $0$,通过该约束去得出不等式组中其他未知数的解。

还有一种是不仅需要判断是否有解,还要求求出一组最大/最小解,这种类型可以考虑通过增加一个点去对其他点进行约束,然后以这个点为源点跑最长/最短路求解,由于差分约束类型题目近几年几乎不可见了,所以基本没遇过这种类型,只能瞎BB下。

SPFA 算法

由于图中可能存在负环,所以不能使用 $dijkstra$ 算法求解,可以考虑使用 $SPFA$ 或者 $Bellman-Ford$,个人建议用 $SPFA$ ,比较快。

最长路与最短路

$SPFA$ 求最长路的算法跟求最短路类似:

  • 最长路是初始化为 $0$,当存在 $dist[v] < dist[u] + cost_{u->v}$ 时进行更新。
  • 最短路时初始化为 $INF$,当存在 $dist[v] > dist[u] + cost_{u->v}$ 时进行更新。

SPFA的优化

另外,有时连 $SPFA$ 算法的玄学时间复杂度都不能承受,可以考虑使用 $SPFA$ 的两个优化:$SLF$ 和 $LLL$。

  • $SLF$: $Small$ $Label$ $First$

使用双端队列$deque$,把将要插入的节点 $v$ 与此时队列中的队首 $u$ 的 $dist$ 进行比较,若小于则插入队首,否则插入队尾。即优先将 $dist$ 较小的节点拿出来松弛操作。

  • $LLL$: $Large$ $Label$ $Last$

讲道理这种优化我也没用到过(。・・)ノ。不过还是简单讲下,这种方法需要维护队列中 $dist$ 的平均值,然后每次出队时(设为 $i$),将 $dist[i]$ 与 $dist_{avg}$ 进行比较,若大于则将 $i$ 节点重新插入队尾,然后继续出队,一直找到一个节点使得 $dist[i] \le dist_{avg}$,将其取出进行松弛操作。

等有空再来补几发代码。

完。

如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!