最短路徑上的變化（複數？）

Question

我有以下問題。給定一個有向圖G =（V，E），所有邊{i，j}之間的邊成本cij。我們有多個來源，比如s1，...，sk和一個目標，比如t。問題是找到從s1，... sk到t的最低組合成本，其中所有不同路徑的訪問頂點總數爲M.（源和目標不計爲已訪問頂點，並且0 < = M < = | V | -k + 1，所以如果M = 0所有路徑直接從源到目標）。

1. 問題是由剛剛扭轉所有的邊緣，使源目標和目標源類似的多重目標（T1，...，TK）和一個源。我認爲這可能是有用的，因爲例如Dijkstra計算圖中從一個源到所有其他頂點的最短路徑。

2. 只有一個目標和一個源，可以找到最大的最短路徑。用Bellman Ford算法計算訪問頂點的數量M.這是通過迭代地增加訪問頂點的數量來完成的。

3. 尋找從一個源到一個目標的最短路徑而需要訪問頂點v1，...，vk的問題對於小k可以如下求解：i）計算所有節點之間的最短路徑頂點。 ii）檢查哪個k！排列是最短的。 我認爲這可能是有用的時，我將調整後的問題1）轉變爲從一個源到一個「超級」的問題，強制訪問「舊」目標t1 = v1，...，tk = vk。

不幸的是，組合1,2和3不提供解決方案，但它可能有所幫助。有誰知道解決方案？這可以有效解決嗎？

Answer 1

爲什麼不爲每個s做​​一個單獨的Dijkstra，然後總結成本？

喜歡的東西：

float totalCost; 
for (int i=0; i<k; i++) 
    totalCost += Dijkstra(myGraph,s[i],t); 

我希望我理解正確的問題。