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