algorithm - 在生成树中找到从单个源到所有其他节点的最短路径的最佳算法

Question

如果我知道给定的图实际上是一个生成树，即每对顶点之间只有一条路径，我如何找到从每个顶点到每个顶点的最短路径？我想要最优化的解决方案。我知道 Dijkstra 算法，但它的时间复杂度很高。

我基本上想从一个源知道每个顶点的距离和路径。鉴于它是一棵生成树，最好和最优化的解决方案是什么？

此外，如果图实际上是生成树，请告诉我是否有一些不同的方法来查找所有对最短路径，而不是多次应用单源最短路径算法。

请注意我的过度解释。

Answer 1

正确的方法是从某个任意节点 N 开始深度优先搜索，这可以在线性时间内完成。每次遇到新节点时，都会记录到达那里的路径。这将为您提供 N 和图中每个其他节点之间的最短路径。

要找到节点 V 和 W 之间的最短路径，您需要查看从 V 到 N 的路径>，以及从 N 到 W 的路径。这将为您提供 V 和 W 之间的最短路径，除了在您点击 N 然后返回的中间可能有一个冗余位再次。例如，假设从 V 到 N 的路径是这样的:

V, A, B, C, D, E, N

从N到W的路径是这样的:

N, E, D, F, G, W

然后你可以看到从 V 到 W 的路径在这些连接之后将到达 D，然后上升到 < em>N 通过 E 并再次返回。这需要从您的路径中删除，以便为您提供最短路径。换句话说，您从第一条路径的末尾向后扫描，然后通过第二条路径向前扫描，直到到达它们共有的最后一个节点(在本例中为 D)，然后将路径并在此时将它们连接在一起，这样你就剩下

V, A, B, C, D, F, G, W

这将为您提供最短路径。您可以看到这一点，因为从 V 到 W 的不重复任何节点的任何路径一定是生成树中的最短路径。

这是从维基百科截取的生成树示例。如果左上角是V，右上角是N，左下角是W，可以看到从开始的最短路径>V 到 W 是从 V 到 N 的最短路径，与从 N 到 W，但在我们到达 N 并返回主路径的中间没有重复的部分。