antivenom's blog

Interesting Graph Problem!!!!
By antivenom, 9 years ago, In English

Hey guys,I just encountered with a very Interesting and tough problem(at least for me).It is asked to calculate second shortest path from node 1 to N.Can anybody have some idea how to solve this with Dijktra's .In case you want to check if I have tried or not see this(yes,I know I have done nothing special but normal dijktras)

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

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

Hint: apply 2 dijkstras one from vertex No.1 and the other from vertex No.n and check every edge Maybe that works just maybe xD

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

    You mean you are also not so sure.

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

      This almost works for all the problems of dijkstra (sorry don't have time to corret my english)

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

        Nobody asked to correct anything sir,you are awesome :).Thank you for suggesting me your approach.Really appreciate that :)

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

          you're welcome btw other's solution works too but this is a nice approach

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

    You mean check, for each edge, if the 2nd shortest path goes through that edge?

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

    I don't understand what you are trying to do in details, but are you handling the case where every path is a shortest path?

    The problem allows you to use an edge more than once...you can't out -1.

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

Let Dv, k be the kth shortest path to node v. Suppose we get to v from the 3rd shortest path to node u, then it means Dv, 2 = Du, 3 + [u, v], where [u, v] denotes the road from u to v. But Du, 1 < Du, 2 < Du, 3, so it means both Du, 1 + [u, v] and Du, 2 + [u, v] are less than Du, 3 + [u, v], which is a contradiction, since Dv, 2 would be at least the 3rd shortest path to v. So we don't need to keep track of more than 2 shortest paths for each node.

I coded a Dijkstra storing the two shortest paths for each node, and I believe it should be OK, but I don't have a way to try it out because I can't register at Light OJ.

Here's the code, just in case: C++ Code

UPDATE: Finally, the login data arrived at my e-mail and I was able to test the code. It got AC, so yes, it's the correct idea.

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

    Don't know why but your solution gives me sense of some sort of DP+Graph problem.Correct me if I am wrong.I am trying what you explained with pen and paper in hope of getting better understanding.Btw can you tell me what is the level of this question.I mean like div2 B or so..

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

      it's like one of the easiest dijkstra's it's actually div 2 D

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

      It's actually a normal Dijkstra, but every node keeps 2 values instead of one. You have to be careful to only consider different distances.

      Difficulty is clearly not Div2 B, but rather around Div 2D.

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

Implement Dijkstra, but instead of keeping just one array Dist, keep two of them — DistActual and DistSecond. Each time you find a shorter path to the node I, move the value from DistActual[i] to DistSecond[i], and place the new shortest path inside the DistActual[i].

And since before start all the DistActual are equal to INFINITY, if there is no second shortest path, the DistSecond[i] will be equal to INF.

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

    There's also the chance that you may need to update only DistSecond and DistActual stays the same.

    → Reply