Given a weighted graph including two nodes $s$ and $t$, some edges can be removed without changing the shortest path from $s$ to $t$. Maybe there is an edge in the graph that, if that edge is removed, the path between $s$ and $t$ doesn't exist anymore.
Describe an efficient algorithm that selects the edge, that if that edge is deleted the length of the shortest path from $s$ to $t$ increases the most (so i.e. it goes from $2$ to $10$).
So it is obvious that I need to delete an edge that is used in the shortest path from $s$ to $t$.
Of course I could delete an edge that is part of the shortest path from $s$ to $t$, then again find the shortest path. I do this for every edge that is in the shortest path and then compare the all the new shortest paths. But this takes way too much time, and it isn't a really efficient algorithms and it isn't mathy.
It is some kind of reverse shortest path algorithm? Could somebody give me a few tips?
Best Answer
I would first compute the shortest $s$-$t$-path $P_{st}$. For nodes $u$ and $v$ in this path let $d(u,v)$ denote the shortest path distance from $u$ to $v$. This distance can be read from $P_{st}$ since the shortest $u$-$v$-path must be contained inside $P_{st}$.
Remove all edges of $P_{st}$ from the graph. In the modified graph run an all pairs shortest path algorithm to obtain distances $d'(u,v)$ for all nodes $u$ and $v$. For all nodes $u$ inside $P_{st}$ compute \begin{align*} D(u) = \min_{v \in P_{st}} d(s,u) + d'(u,v) + d(v,t) \end{align*} This value tells you the length of shortest $s$-$t$-path if edge $(u,u') \in P_{st}$ is removed from the graph. Note that $u'$ is the next node after $u$ in $P_{st}$ and is not necessarily identical to the node $v$ which achieves the minimum.
I guess this is not yet as mathy as you would prefer, however at least you do not obviously enumerate all solutions (though, in principle you still do).