确定从s到t的所有最短路径是否都包含边e

本文介绍了确定从s到t的所有最短路径是否都包含边e的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

Let G = (V;E) be a directed graph whose edges all have non-negative weights. Let s,t be 2 vertices in V, and let e be an edge in E. Describe an algorithm that decides whether all shortest paths from s to t contain the edge e.

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

Well, this is how you can achieve Dijsktra's time complexity: Simply run Dijkstra from s and calculate delta(s,t) (the weight of the shortest path from s to t). Remove the edge e, and run Djikstra again from s in the new graph. If delta(s,t) in the new graph has increased, it means that all shortest paths from s to t contain the edge e, otherwise it's not true.

我想知道是否有更有效的算法来解决此问题。您是否认为有可能战胜Dijkstra的时间复杂性？

I was wondering whether there is a more efficient algorithm for solving this problem. Do you think that it's possible to beat Dijkstra's time complexity ?

预先感谢

推荐答案

您的方法对我来说是正确的。您只需计算出最短路径即可，也可以不计算边缘e。这样就可以进行2次Dij​​kstra搜索。

Your approach sounds correct to me. You just calculate the shortest path with and without the possibility of taking edge e. That gives you 2 Dijkstra searches.

如果您使用A *，双向搜索或恢复Dijkstra搜索树，则还有改进的空间：

There is room for improvement if you go to A*, bidirectional search or recover your Dijkstra search tree:

• A *可以加快Dijkstra查询的速度，但对于您的图形来说可能是不可能的，因为您需要能够在剩余距离上定义一个好的界限。 / li>
• 可以在两个搜索都在边缘附近进行双向搜索。然后，您可以使用仅1个快速双向查询+两种情况下的一些额外工作来检查带有和不带有边缘的所有路径，而不用拥有两个非常相似的完整Dijkstra
• 边缘并维护您的搜索树。然后添加e并从e的起点开始更新最短路径树。如果终点的标签>起点的标签+长度e，则使用e时可以更快地到达终点。递归搜索端点的邻居，并仅在可以比以前更快地到达的情况下更新距离。应该可以为您节省一些工作。