Biggest increase of shortest path after deleting an edge. 
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?
 A: 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).
A: A variant of Dijkstra's algorithm should do it.  You can combine your search for "shortest path without using edge $e$" with your search for the shortest path overall.  To do so, maintain a table where you record, for each edge $e$, the shortest path that avoids using edge $e$. The algorithm is as follows.


*

*Initialize a list CUTS to be the set of all edges in the graph.
Initialize a table CUT-PATH-LENGTH, associating each edge $e$ with the length of the shortest path from the start to the goal that avoids edge $e$. These values are all initially $\infty$, indicating that no path has been found at all.
Initialize SHORTEST-PATH-OVERALL to null.
Initialize an AGENDA containing the initial singleton path.

*While the agenda is not empty and the CUTS list is not empty:


*

*Remove the first path from the agenda.

*If that path leads to the goal, compute its length $\ell$. For every edge $e$ in CUTS, excluding edges in the path, set the entry CUTS-PATH-LENGTH[$e$] = $\ell$. Then remove $e$ from CUTS.
If this was the first time a path to the goal was found, it's the shortest path overall. Store it as SHORTEST-PATH-OVERALL.

*Compute all loopless one-edge extensions of the path. Add them to the agenda, then sort the agenda in increasing order of length.


*When the loop terminates, the shortest path (as well as its remove-one-edge  runner-ups) are stored in the table CUT-PATH-LENGTH. 
If SHORTEST-PATH-OVERALL was not found, then the start and end node are actually disconnected to begin with. Removing an edge won't make a difference.
If SHORTEST-PATH-OVERALL was found, then for each edge $e$ in the path, the entry CUT-PATH-LENGTH[$e$] records the length of the shortest path between the start and end nodes when edge $e$ is removed. Find the edge corresponding to the largest such value and return it. 
(In particular: if the loop terminated while CUTS was non-empty, then removing any edge in CUTS causes the start and end nodes to become disconnected, so you can immediately return any one of those edges.)
