Second shortest path

Problem

Given a simple weighted graph $G=(V,E)$ (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 $\pi_1(i,j)$ denote the shortest path between the vertices $i$ and $j$ . The shortest path between a vertex and itself is zero. If there is no path between $i$ and $j$ then $\pi_1(i,j)=\infty$ .

Now use the following algorithm to obtain all-pairs second shortest paths. We will denote the second shortest path between a pair of vertices $i$ and $j$ as $\pi_2(i,j)$ . Initially $\pi_2(i,j)=\infty$ for any pair of vertices $(i,j)$ .

For each edge $(x,y)$ in $E$
$\$ For each pair of vertices $(i,j)$ in $V\times V$
$\$ $\$ Let the path $tmp(i,j)$ be the concatenation: $\pi_1(i,x)$ , $(x,y)$ , $\pi_1(y,j)$
$\$ $\$ If $len(\pi_1(i,j)) < len(tmp(i,j)) < len(\pi_2(i,j))$
$\$ $\$ $\$ $\pi_2(i,j)=tmp(i,j)$

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 $i$ and $j$ , we try to find all paths between $i$ and $j$ that is composed of a sequence of right steps (the shortest path between $i$ and some reachable vertex $x$ ) followed by an arbitrary step that could be our mistake (the edge $(x,y)$ ) then another sequence of right steps (the shortest path between $y$ and $j$ ). 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.

About these ads

Written by Hatem Abdelghani

July 4, 2009 at 2:24 am

Posted in Problem Solving

Tagged with Algorithms, Graph Theory, Online Judge, UVa

10 Responses

Subscribe to comments with RSS.

Nice description.

vertexone

November 23, 2009 at 5:33 am

Reply
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 AbdElMonem

December 18, 2009 at 12:39 pm

Reply
- A direct generalization to the $N^{th}$ shortest path will be:
  
  For $k=2$ to $N$
  $\$ For each edge $(x,y)$ in $E$
  $\$ $\$ For each pair of vertices $(i,j)$ in $V\times V$
  $\$ $\$ $\$ Let $tmp(i,j)$ be the concatenation: $\pi_{1}(i,x)$ , $(x,y)$ , $\pi_{1}(y,j)$
  $\$ $\$ $\$ If $len(\pi_{k-1}(i,j)) < len(tmp(i,j)) < len(\pi_{k}(i,j))$
  $\$ $\$ $\$ $\$ $\pi_{k}(i,j)=tmp(i,j)$
  
  That is, we will make a loop from $k=2$ to $N$ 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 $len(\pi_{k-1}(i,j))$ rather than $len(\pi_{1}(i,j))$ .
  
  But probably there are other ways to do it more efficiently.
  
  Hatem Abdelghani
  
  December 18, 2009 at 8:57 pm
  
  Reply
  - 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?
    
    Troper
    
    August 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 Abdelghani
    
    August 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?
    
    Troper
    
    August 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 Abdelghani
    
    August 26, 2012 at 4:46 am
how to perform this in java?

shash

September 25, 2012 at 9:34 am

Reply
- This is suboptimal. You can solve this problem using a Topological Sort and then Dynamic Programming for O(V+E)
  
  marco
  
  December 16, 2012 at 7:53 pm
  
  Reply
  - http://courses.csail.mit.edu/6.006/oldquizzes/solutions/final-f2009-sol.pdf
    See problem 6
    
    marco
    
    December 16, 2012 at 7:56 pm

Yet Another Blog

Second shortest path

Like this:

10 Responses

Leave a Reply Cancel reply

Archives

Meta

Tags

Follow “Yet Another Blog”