0

令 G = (V;E) 是一个有向图，其边都具有非负权重。设 s,t 是 V 中的 2 个顶点，设 e 是 E 中的一条边。描述一种算法，该算法确定从 s 到 t 的所有最短路径是否包含边 e。

好吧，这就是实现 Dijsktra 时间复杂度的方法：只需从 s 运行 Dijkstra 并计算 delta(s,t)（从 s 到 t 的最短路径的权重）。删除边 e，然后从新图中的 s 再次运行 Djikstra。如果新图中的 delta(s,t) 增加了，则说明从 s 到 t 的所有最短路径都包含边 e，否则不成立。

我想知道是否有更有效的算法来解决这个问题。你认为有可能打败 Dijkstra 的时间复杂度吗？

提前致谢

4

1 回答 1

1

你的方法对我来说听起来是正确的。您只需计算有和没有可能获得边 e 的最短路径。这为您提供了 2 个 Dijkstra 搜索。

如果你去 A*，双向搜索或恢复你的 Dijkstra 搜索树，还有改进的空间：

  • A* 会加快您的 Dijkstra 查询，但您的图表可能无法实现，因为您需要能够定义剩余距离的良好界限。
  • 双向搜索可以通过两个搜索在边缘相遇来完成。然后，您可以检查所有带有和不带有边缘的路径，只需 1 个快速双向查询 + 两种情况下的一些额外工作，而不是拥有 2 个非常相似的完整 Dijkstra
  • 您可以在没有边缘的情况下搜索一次并维护您的搜索树。然后添加 e 并从 e 的起点开始更新最短路径树。如果终点标签>起点标签+长度e，则使用e可以更快到达终点。递归搜索端点的邻居，只有在可以比以前更快地到达时才更新距离。应该为您节省一些工作。
于 2013-03-04T09:57:37.713 回答