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?