Decide Whether All Shortest Paths From s to t Contain The Edge e

Question

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.

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.

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 ?

Thanks in advance

Answer 1

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.

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

• A* would speed up your Dijkstra-query but it might not be possible for your graph as you need to be able to define a good bound on your remaining distance.
• bidirectional search could be done with both searches meeting around the edge. You can then examine all paths with and without the edge with only 1 fast bidirectional query+ some extra work for both cases instead of having 2 full Dijkstra's that are very similar
• you could search once without the edge and maintain your search tree. Then you add e and update the shortest path tree starting from the start point of e. If the label of the end point > the label of the start point + length e, the end point can be reached faster when using e. Recursively search the neighbours of your end point and only update the distances if they could be reached faster than before. Should save you some work.