1
$\begingroup$

The question asks to write an algorithm using Dijkstra's algorithm with time complexity of

$\Theta(|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)}.$

  7. 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, and that's why I used the loop in line 6.

$\endgroup$
8

0

Browse other questions tagged or ask your own question.