5

存在诸如 Bellman-Ford 算法和 Dijkstra 算法之类的算法来找到从图上的单个起始顶点到每个其他顶点的最短路径。但是，在我正在编写的程序中，起始顶点的变化比目标顶点的变化要频繁得多。有什么算法可以反过来 - 即给定一个目标顶点，从每个起始顶点找到最短路径？

4

2 回答 2

10

只需反转所有边，并将目的地视为起始节点。问题解决了。

于 2015-02-27T19:33:43.950 回答
1

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

于 2015-02-27T19:34:59.180 回答