多源單目標算法

Question

我有一個圖表，我需要找到從多個來源到單個目標的距離。我知道如何使用dijkstra的算法找到單個來源到多個目的地。

我發現了一個公認的答案在這裏：Algorithm like Bellman-Ford, only for multiple start, single destination?

但我不明白爲什麼它會奏效。誰能解釋爲什麼這個答案有效？

Answer 1

它的工作原理，因爲如果你有一個（原始）來源s，和你的目標t - 在修改後的圖形，你反向邊緣，找到t的最短路徑的所有節點，包括s。

此路徑是t->v1->v2->...->vk->s

每個邊（u，v）的在此路徑中存在當且僅當存在原始圖(v,u)的邊緣，所以在翻轉圖中的上面的路徑可以直接轉換到路徑：

s->vk->vk-1->...->v2->v1->t 

路徑的權重是相同的，並且沒有更短的路徑，否則 - 您會在反轉圖上找到它。

---

作爲邊注，我個人更喜歡通過創建一個新的虛擬節點x變換多個源問題單一來源問題，並創建從x的邊緣到任何與0重量源，然後運行最短路徑算法，以x作爲源。
（假設你需要的是從某個源到目標的最短路徑）