0

Let's say I have a directed weighted graph $G=(V,E)$ where the weights are all positive.

Let $d_G(s,t)$ be the value of the shortest path in $G$ between two nodes $s$ and $t$. I want to find the set of edges $E' \subset E \ $ whose removal would increase the value of the shortest path between $s$ and $t$. $ \\ $ i.e $\ E' = \{e \in E : d_{G-e}(s,t) > d_G(s,t)\}$.

I know that a possibility would be to run Dijkstra in $G$ to find all edges in the shortest path between $s$ and $t$ and then remove these edges one at a time from $G$ and rerunning Dijkstra in the new graph to see if the value of the shortest path increases. However this is quite inefficient. Is there a better solution?

Peter Sampodiras
  • 437

1 Answers1

0

There is a better solution indeed. Run Dijkstra two times, the first one to get the shortest path from $s$ to every vertex and the second one to get the shortest path from all vertices to $t$. Now you can find all shortest paths from $s$ to $t$. Now consider all of the edges in these paths. The edges that appear in all of them are the ones you are looking for, since removing them would increase the value of any shortest path from $s$ to $t$.

Peter Sampodiras
  • 437