最短路徑變化

Question

我正在尋找解決以下問題，與最短路徑有關的問題。給定一個有向圖G =（V，E），源s，目標t 1，t 2，...，tk，並且行進邊{i，j}的成本爲cij。現在我想知道從s到t1，...，tk的最短路徑。但是，如果使用vertext v _i（不是源或目標），那麼我們有額外的成本C.請注意，兩條路徑使用相同的vertext vi，成本C只支付一次。

Answer 1

標準爲O（n^3）動態規劃解決方案...

http://en.wikipedia.org/wiki/Dijkstras_algorithm

...仍然有效，只有一個小的調整：

纔算直接鄰接矩陣成本，然後通過考慮快捷方式進行迭代，但是在計算vi上的快捷方式添加成本時。

創建修改weightning功能：

w'(u,v) = w(u,v) + C if v == c 
w'(u,v) = w(u,v)  otherwise 

不難看出，

Answer 2

如果您正在尋找最短路徑，每條路徑是，如果用c然後penaltised當運行dijkstra's algorithm或Bellman Ford時，使用w'任何使用c的路徑都會受到C的懲罰，因爲如果c出現在路徑中 - 它看起來只有一次，因此C被添加到總重量中[注意c在最短路徑中不能出現多次]，當然如果c未在此路徑中使用，則不會有任何處罰。

---

編輯：我不知道我的理解正確，如果有什麼@SaeedAmiri被提的是正確的，並且如果你想給的懲罰只有一次[和路徑總和最小化到T1， ...，TK]那麼你應該使用不同的解決方案 - 用類似的想法：

創建weightning函數w」，使之：

w'(u,v) = w(u,v) + C + epsilon if v == c 
w'(u,v) = w(u,v)     otherwise 

注意，重要的是小量是一個小尺寸，只能在w'上實現，並且尺寸最小。與w圖表

1. 運行Dijkstra算法或BF，讓我們表示權重，如結合w'圖表 W1
2. 運行Dijkstra算法或BF讓我們表示權重W2
3. 如果W1[ti] == W2[ti]每個TI ∈ {t1，...，tk} - 那麼最短路徑中不需要c，總結果是SUM(W1[ti])
4. 否則 - 結果爲min {SUM（W1 [ti]）+ C，SUM（W2 [ti]）`

落後第4步的想法是你有兩種可能性：

• 你可以得到所有的T1，...，TK不使用c，它會更便宜，然後使用具有路徑它，所以你返回W2的總和。
• 或者，如果忽略c - 只會更加寬廣 - 因此您可以自由使用它[並返回W1的總和]，並僅添加一次懲罰。

Answer 3

你還沒有告訴我們到底是什麼問題，但有一個明確的片段，承認了一個保守的客觀保留減少。

對於集合封面的任意實例，爲每個集合設置一個包含源，頂點和每個元素頂點的圖。終端t1，...，tk是元素頂點。每個集合頂點的權重爲0的邊和與其元素對應的頂點的權重爲零。在這張圖上，我們必須購買一套封面以便從源頭到達終端，並且每套封面都足夠了。

除非有你可以告訴我們的關於你的實例的東西，多項式時間算法的近似比率不會比Theta（log n）好，所以我建議整數編程。