类似Bellman-Ford算法，但适用于多个起点和单个目的地的算法是什么？

Question

5

像Bellman-Ford算法和Dijkstra算法这样的算法存在于寻找从图上单个起始顶点到每个其他顶点的最短路径中。然而，在我编写的程序中，起始顶点的变化要比目标顶点更加频繁。有没有一种算法可以反过来--即给定单个目标顶点，从每个起始顶点找到最短的路径呢？

- flarn2006

如果你的节点经常变化，也可以考虑使用Roy-Floyd算法。 - IVlad

2个回答

1

如果这是一个无向图：我认为倒置问题会给你带来优势。将实际目的地视为起点，并找到从该起点到图中所有其他节点的最短路径。通过这样做，您可以使用传统的路径算法。

- Andrew_CS

1

这样表述（而不是反转边缘）假设距离是对称的（这可能没问题，只是要记住这一点）。 - harold

@harold 如果边缘有权重，那就是真的 - 我没有假设会有边缘权重，因为 OP 没有提到它们。 - Andrew_CS

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pham Trung · Accepted Answer

10

只需翻转所有边，将目的地视为起始节点。问题得以解决。

- Pham Trung

1

我简直不敢相信我没想到那个。我会试一下，很可能会把你的答案标记为已接受（因为你回答得最快）。谢谢！ - flarn2006

很棒的答案 :))) - DmitrySemenov