确定从s到t的所有最短路径是否都包含边e [英] Decide Whether All Shortest Paths From s to t Contain The Edge 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次Dijkstra搜索。
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时可以更快地到达终点。递归搜索端点的邻居，并仅在可以比以前更快地到达的情况下更新距离。应该可以为您节省一些工作。
这篇关于确定从s到t的所有最短路径是否都包含边e的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
