0

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

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

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

请注意我的过度解释。

4

2 回答 2

3

正确的方法是从任意节点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 ，然后通过E上升到N并再次返回。这需要从您的路径中删除，以便为您提供最短路径。换句话说，您从第一条路径的末端向后扫描，并通过第二条路径向前扫描，直到到达它们共有的最后一个节点（在这种情况下为D），然后您将路径切断并将它们连接在一起点，这样你就剩下

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

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

这是一个从 Wikipedia 截取的生成树作为示例。如果你把V作为左上角，N作为右上角，W作为左下角，你可以看到从V到W的最短路径是从V到N的最短路径，与从N到W的最短路径连接，但是中间没有重复的部分，我们向上到N并返回到主路径。

生成树示例

于 2014-12-11T19:55:11.517 回答
2

最佳解决方案：

  1. 选择一个任意顶点作为根并从中运行深度优先搜索以计算dist[i]所有i- 根和i第 - 个顶点之间的距离。

  2. u两个任意顶点和之间的距离v是dist[u] + dist[v] - 2 * dist[lca(u, v)]，其中lca(u, v)是 和 的最低公共u祖先v。

第一步具有O(n)时间复杂度。第二步的时间复杂度取决于最低公共祖先搜索实现。可以通过线性预处理时间实现O(1)每个查询（使用此算法：http ://www3.cs.stonybrook.edu/~bender/newpub/BenderFa00-lca.pdf ），但这种方法有一个相当大的常数，它不是很容易实现。该解决方案是最佳的，因为它需要O(n)时间进行预处理（不可能做得更好，因为您至少必须读取输入）并且它会在恒定时间内回答查询。您还可以使用更简单的算法获得O(log n)每个查询的时间O(n)或O(n log n)预处理时间。

于 2014-12-11T20:06:11.477 回答