※ 引述《qazzwsx (qazzwsx)》之铭言： : 最近看到一个bellman-ford 求最短路径的演算法 : 他的其中一个应用是用来解一组联立不等式 : 解法是先在原图中加入一个新节点v , 并令v到图上各节点的距离为0 : 然後用bellman-ford演算法解这个新节点v到图上各点的最短路径 : 即为联立不等式的解 : 请问有人知道为什麽要令距离为0吗? : 不为零可以吗? 不知道你看的是不是 introduction to algorithms 假设如书上的举例, 每个未知数指的是某件事发生的时间 而某个 constraint xi - xj <= bij 的意思是 xi 的事件发生要在 xj 事件发生再 bij 时间之前 (bij 可以是正负) 我们要找一组 X = (x1, .. xn) 符合给定的 constraint 其实就要找到某个时间发生的关系, 符合上述时间的限制 但是, 这些事件发生的时间都是相对的 (课本上也有证明, Ax<=b 是一组解, x+d 也会是一组解) 因此, 我们需要一个基础时间: 0 而 v0 就担任了这个角色 它到各结点距离也都是 0, 意谓着每个事件初始条件同时开始 之後用 bellman-ford 再去调整各别的 constraint 之下 事件发生的时间的调整 (且这又刚好 map 到最短路径上) 当然你也可以令这个基础时间为任意 constant d 也就是它到每一个节点都要一样是 d -- 重点是都要一样 不然意谓着这些事件先天上又有限制 没有同时开始的自由 -- 有时候，遗忘，是令人快乐的。什麽时候？当然是有人伤了你的心的时候。 　存心伤你的那个人，固然是故意和你过不去，但是被伤了心而耿耿於怀的你 　，却是和自己过不去了。所以，记性不好的人，通常会是比较快乐的人，也 　是比较不容易被击倒的人。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.55 ※ 编辑: ledia 来自: 140.112.30.55 (05/03 15:28)