# The second shortest path on a directed graph [closed]

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:

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.

• – D.W.
Commented Nov 30, 2023 at 18:54
• Thank you very much! Commented Nov 30, 2023 at 23:31
• @Daniel from the last link, it appears your question is only feasible for an undirected graph, and your algorithm is the best for a directed graph. do you think so? Commented Jan 3 at 13:22
• Hello! I don't think so. I know that question asked to use Dijkstra's algorithm. There for the graph must be directed. By the way, my algorithm is with a time complexity that is more costly than the time complexity the question asked for :( Commented Jan 3 at 19:24
• – D.W.
Commented Jan 30 at 18:30