多源单目的地算法

Question

我有一张图，需要找出从多个起点到单个终点的距离。我知道如何使用迪杰斯特拉算法找到单个起点到多个终点的距离。

在这里我找到了一个被接受的答案：Algorithm like Bellman-Ford, only for multiple start, single destination? 但是我不明白为什么它能够工作。能否有人解释一下这个答案为什么能够工作？

- user2517419

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作为源运行最短路径算法。 （假设您需要的是从某个源到目标的最短路径）

- amit

---

谢谢你的回答，这个侧注会对我很有帮助。 - user2517419