多源单目标算法

Question

我有一个图表，我需要在其中找到从多个源到单个目的地的距离。我知道如何使用 dijkstra 算法找到单一来源到多个目的地。

我在这里找到了一个可接受的答案：

但我不明白为什么它会起作用。谁能解释为什么这个答案有效？

Answer 1

之所以有效，是因为如果您有一个（原始）源 s 和您的目标 t - 在修改后的图中，您可以反转边缘并从 [=12= 找到最短路径] 所有节点，包括 s.

这条路径是t->v1->v2->...->vk->s

这条路径中的每条边(u,v)存在当且仅当原图中有一条边(v,u)，所以上述倒转图中的路径可以直接转化为一条路径：

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

路径的权重相同，没有更短的路径，否则 - 你会在反转图中找到它。

---

作为旁注，我个人更喜欢通过创建一个新的虚拟节点 x 将多源问题转换为单源问题，并创建一条从 x 到任何源的边权重0，然后运行以x为源的最短路径算法。
（假设你需要的是从某个源到目标的最短路径）