Searching...
有时候我们需要维护一些具有传递性的关系，如相等，连通等。
初始条件往往是给定几组关系，要把所有的关系求出来。
可以把 Floyd 算法做一些调整：
但是 Dijkstra 算法要求所有边权均非负，于是就有了重赋权的技巧。
接下来证明这样做为什么是对的：
首先有定义 ：
差分约束是用来解形如 \(x_{1}-x_{2}\leqslant k\) 的若干个方程的算法。
另外，如果有负环则无解。
时间复杂度 \(\Theta(\rm SPFA)\)。
需要注意的是，最短路求的是以起始点为基准的最大解，而最长路求的是以起始点为基准的最小解。