determinism's blog

Second Shortest Path
By determinism, 9 years ago, In English

I've come across to this problem on UVa. It basically asks for second shortest path. I've looked it up on the internet, but I couldn't find any practical implementation of it. Are there any good tutorial on this topic?

Note: I'm asking about both SSP and APSP. Also, is second shortest path simpler than more general kth shortest path algorithms in terms of complexity?

UPD: Thank you really much for your help, I've solved the problem! But the thing is nobody has mentioned any algorithm for All-Pair Second Shortest Path problem yet. Can someone who is knowledgeable about this problem explain it?

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (17)
| Write comment?
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

if there is another shortest path will it be the second shortest path?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    No, its distance should be higher for this problem.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Ok u do a dijkstra after that for every edge if its incident vertices are u,v and the start and end are a and b u check this if(dis[a][u] + weight[u][v] + dis[v][b] != shortest && same thing < second_shortest) second_shortest = that thing uneed a dijkstra for a and a dijkstra for b

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 3   Vote: I like it -15 Vote: I do not like it

        Is this solution correct? I have implemented it for 3255 roadblocks POJ , but at two test cases answers are different, Are you sure?

        For those who gave me negative , please write correctness proof of this , I couldn't figure out .

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://en.wikipedia.org/wiki/Yen's_algorithm

How about this?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you! The thing is these implementations are more kind of a general and real life implementations. Is there any shorter implementation in competitive programming paradigm? Also, what about for APSP?

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you post the statement because I can't open UVa now, please? Is the graph directed? Can the path contain cycles?

PS: Am I the only one who cannot open UVa?

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hello again! I just got accepted, let me explain my idea not only for the second but for the K-th shortest path in a graph:

We are going to use a modified Dijkstra's algorithm. We will store vectors for each node containing the distances(instead of an array dist[i] for each node i).

Assume that we are using the standard Dijkstra's algorithm implemented with a priority queue. We will use this structure for the queue:

struct el
{
    int vertex,cost;
    el(){}
    el(int a, int b)
    {
        vertex=a;
        cost=b;
    }
    bool operator<(const el &a) const
    {
        return cost>a.cost;
    }
};

At each step we take the element on the top of the queue. We will push the current distance in the vector in two cases:

1) If the vector with the distances is empty

or

2) If the vector has one element inside and the current distance is greater than the first:

curr=pq.top();
pq.pop();
if(dist[curr.vertex].size()==0)
    dist[curr.vertex].push_back(curr.cost);
else if(dist[curr.vertex].back()!=curr.cost)
    dist[curr.vertex].push_back(curr.cost);

Then we go through curr.vertex's children. If the current children has already have two elements in its vector, then we skip it. Otherwise, we find the current distance to reach it from curr.vertex and push it in the queue.

My code is here: http://ideone.com/QpWFnR

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    I got it! Thank you really much! It seems like we can't use this idea to Floyd-Warshall, can we?

    UPD: Is this algorithm's complexity O(k*(V+E)*logV) using binary heap?

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks Bro....Really helped

    Thanks a lot

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

But the thing is nobody has mentioned any algorithm for All-Pair Second Shortest Path problem yet.

All-pair shortest path can be done running N times Dijkstra's algorithm. Then all-pair second shortest paths can be done running N times the modified Dijkstra's algorithms. The complexity is O(2*(V*logV + E)) = O(V*logV + E) per run which is the same as the normal Dijkstra.

Is that what are you asking?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thank you again for your fast response.

    I think O(V*k*(V*logV + E)) is correct for fibonacci heap. Its complexity becomes O(V*k*(V+E)*logV) = O(k*V^3*logV) when E = V^2 and using binary heap. It also doesn't work on a graph with negative weights. What I'm asking for is something like Floyd-Warshall which can work on a graph with negative edges weights, negative cycles and also something with a complexity of O(k*V^3) or something similar.

    → Reply