如何运用Bellman和SPFA算法学习差分约束系统？

本文共计2237个文字，预计阅读时间需要9分钟。

差分约束系统[概念]：对一个序列，给定m个不等式，形如a+b=k，同时满足这m个不等式，求解是否存在。

[学习]：我是通过一个三角形不等式看懂的。

例如以下三个不等式：（摘自上面）

差分约束系统

：对于一个序列。

给出m个不等式，形如a+b<=k

问，同时满足这m个不等式的解存不存在。

：

我是通过一个三角不等式看懂的。

如下三个不等式：（摘自上述博客）

B - A <= c (1)

C - B <= a (2)

C - A <= b (3)

我们想要知道C - A的最大值，通过(1) + (2)，可以得到 C - A <= a + c，所以这个问题其实就是求min{b, a+c}。 将上面的三个不等式按照 三-1 数形结合

图三-2-1

三角不等式。将三个不等式推广到m个，变量推广到n个，就变成了n个点m条边的最短路问题了。