※ 引述《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)