Yet Another Blog

Second shortest path

with 10 comments

Problem

UVa – 10342

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

10 Responses

Subscribe to comments with RSS.

  1. Nice description.

    vertexone

    November 23, 2009 at 5:33 am

  2. 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

    • 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

      • 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

  3. how to perform this in java?

    shash

    September 25, 2012 at 9:34 am


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: