The question asks to write an algorithm using Dijkstra's algorithm with time complexity of
Θ(|E| log|V| ) that find the second shortest path between s∈V and t∈V.
The farthest I managed to get is:
1.Run Dijkstra's algorithm and find the path from $s$ to $t$. Mark this path as $P_{(s,t)}$.
2.Remove one edge $e' \in E$ in $P_{(s,t)}$.
3.Run Dijkstra's algorithm on $G' = (V, E – \{e'\})$ and find the path from $s$ to $t$. Mark this
path as $P'_{(s,t)}$.
4.Define $\text{secondMin} = |P'_{(s,t)}|$.
5.Define $\text{secondPath} = P'_{(s,t)}$.
6.for $i = 1$ to $|P_{(s,t)}| – 1$:
a. Remove one edge $e \neq e' \in E$.
b. Run Dijkstra's algorithm on $G'' = (V, E – \{e\})$ and find the path
from $s$ to $t$. Mark this path as $P''_{(s,t)}$.
c. if $|P''_{(s,t)}|<$ secondMin then secondMin = $|P''_{(s,t)}|$ and
secondPath = $P''_{(s,t)}.$
- Return $\text{secondMin}$ and $\text{secondPath}$.
The time complexity of the algorithm is mainly achieved by the loop in line 6:
$$\sum_{i=1}^{\Theta(|V|)} \Theta(|E| \log |V|) = \Theta(|V||E| \log |V|)$$
I will tell you where I got stuck:
here is an example for a graph I tried to work with
It can be shown that each edge on the shortest path between s to y, is the shortest edge between two nodes in the path.
I can't see the point when Dijkstra's algorithm gives the second shortest path (if it does at all).
In order to get the second shortest path, I know that one green edge on the left need to be removed, but I don't know which one, so that why I use the loop in line 6.
Best Answer
(I give up giving hints, just write the full solution here.)
Firstly we consider a solution for the problem of the second smallest element in a sequence $a_1, a_2, \ldots, a_n$ subject to reading each element once and having $\mathrm O(1)$ of additional memory.
Let's solve this problem not only for the whole sequence, but also for every its prefix. (Due to the limited amount of memory the answer for a certain prefix will exist for $\mathrm O(1)$ of time only.) We will also compute the minimum for each prefix.
Let's start with an empty sequence. Then both the minimum and the second smallest element are infinite: $m_1 \gets +\infty$, $m_2 \gets +\infty$.
If $m_1$ and $m_2$ are correspondingly the minimum and the second smallest element among the first $i - 1$ elements ($1 \le i \le n$), then for the first $i$ elements there are three options we need to distinguish: $a_i$ is the minimum (the answer is $(a_i, m_1)$), $a_i$ is the second smallest element (the answer is $(m_1, a_i)$) and $a_i$ is greater than the second smallest element (the answer is $(m_1, m_2)$). So we can firstly compare $a_i$ with $m_2$: if $a_i < m_2$ then $m_2 \gets a_i$. Secondly if $m_2 < m_1$ then swap them: $m_1 \leftrightarrows m_2$. Now $m_1$ and $m_2$ are correspondingly the minimum and the second smallest element among the first $i$ elements.
Now let's return to the problem of the second shortest path from $s$ to $t$. The main similarity with the previous problem is that we compute lengths of both shortest and the second shortest paths for each vertex $v$.
So for each vertex $v$ we start with infinite upper bounds on the lengths of both the shortest and the second shortest paths: $b_1(v) \gets \infty$, $b_2(v) \gets \infty$. The only exception is $b_1(s)$ which is $0$.
After that we repeatedly select minimum among non-frozen bounds (all $b_1$'s and $b_2$'s together), freeze it and relax along each outgoing arc (e. g., update bound for the head of the outgoing arc). Updating bounds is completely the same as updating $m_1$ and $m_2$ in the problem of the second smallest element. (Note that it is not possible to update $b_1(u)$ using $b_2(v)$ if $b_1(v) < b_2(v)$, because in such case $b_1(u)$ would be already updated with a smaller number.)
In this way we twice more times select minimum among twice more bound, and relaxation along each outgoing arc will be produced twice. So the total time with binary heap is $\mathrm O(2n \cdot \log 2n + 2m \cdot \log 2n) = \mathrm O((n + m) \log n)$, where $n$ is the number of vertices and $m$ is the number of arcs. If $n = \mathrm O(m)$, that is the case particularly for connected graphs, then it can be simplified to $\mathrm O(m \log n)$. Note that the multiplication constant under big-$\mathrm O$ is at least twice higher, than for the shortest path length.
To reconstruct the second shortest path itself it is possible either saving last successful incoming relaxation for each vertex, or starting from the end search for the previous vertex of the path traversing each incoming arc in the opposite direction. The first option increases the multiplication constant in total time, while the second one adds extra $\mathrm O(m + n)$ time. But the first option allows to reconstruct multiple paths faster, than the second one.