## Second shortest path

**Problem**

Given a simple weighted graph (having no loops and no multi-edges), we want to find for every two vertices a path between those vertices whose length is strictly greater than the length of the shortest path between them but still less than or equal to the length of any other path between them. Loops are allowed in our target path.

**Solution**

First use Floyd-Warshall to obtain shortest paths between all pairs. Let denote the shortest path between the vertices and . The shortest path between a vertex and itself is zero. If there is no path between and then .

Now use the following algorithm to obtain all-pairs second shortest paths. We will denote the second shortest path between a pair of vertices and as . Initially for any pair of vertices .

**For each edge in
For each pair of vertices in
Let the path be the concatenation: , ,
If
**

The rationale behind that algorithm is as follows: Moving from a source vertex to a target vertex, if -at each vertex along our path- we move from our current vertex to an adjacent vertex that lies on the shortest path between the current vertex and the target vertex, we will eventually reach the target vertex throught shortest path. If, at one step, we made a mistake by moving to an adjacent vertex that doesn’t lie on the shortest path between the current vertex and the target vertex, we won’t reach our target vertex throught the shortest path. We need to know which wrong step will make us arrive through a path that is worse than the shortest path but still better than any other possible path. We also know that we have to make no more than one mistake since two mistakes will give us a path that is even worse than the second shortest path. So, for each pair of vertices and , we try to find all paths between and that is composed of a sequence of right steps (the shortest path between and some reachable vertex ) followed by an arbitrary step that could be our mistake (the edge ) then another sequence of right steps (the shortest path between and ). We search all such possible paths for a path that is longer than the shortest path (obtained through Floyd-Warshall) but still shorter than the rest.

Nice description.

vertexoneNovember 23, 2009 at 5:33 am

Does it mean if I want the Nth shortest path I have to apply this algorithm N-1 times, and in each step from(i=2 to N) the temp path will be the concatenation of the (i-1)shortest paths?

Mohamed AbdElMonemDecember 18, 2009 at 12:39 pm

A direct generalization to the shortest path will be:

For to

For each edge in

For each pair of vertices in

Let be the concatenation: , ,

If

That is, we will make a loop from to and in each iteration we still will concatenate the first shortest paths; but we will be looking for a shortest path whose length is greater than rather than .

But probably there are other ways to do it more efficiently.

Hatem AbdelghaniDecember 18, 2009 at 8:57 pm

But, using this method, wouldn’t we probably find more than just the second shortest? I mean, we should, in most cases, find at least the third and the fourth too. Am I wrong?

TroperAugust 24, 2012 at 10:13 am

The generalized form can compute the N-th shortest path, for any N, up to the number of edges in the graph.

Hatem AbdelghaniAugust 24, 2012 at 5:02 pm

I mean, the generalized form surely computes the Nth shortest path, but, if all the possible (x,y) are not of the same lenght, we should find the third, fourth, etc. shortest path even with the non-generalized form, am i wrong?

TroperAugust 24, 2012 at 7:21 pm

I think yes, you are right.

Actually, the generalization that I mentioned above is not general enough, because we can still find higher-order shortest paths by making more than one wrong step, once we are done with all shortest paths that can be obtained by making one wrong step.

Hatem AbdelghaniAugust 26, 2012 at 4:46 am

how to perform this in java?

shashSeptember 25, 2012 at 9:34 am

This is suboptimal. You can solve this problem using a Topological Sort and then Dynamic Programming for O(V+E)

marcoDecember 16, 2012 at 7:53 pm

http://courses.csail.mit.edu/6.006/oldquizzes/solutions/final-f2009-sol.pdf

See problem 6

marcoDecember 16, 2012 at 7:56 pm