Блог пользователя antivenom

Interesting Graph Problem!!!!
Автор antivenom, 9 лет назад, По-английски

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)

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You mean you are also not so sure.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          → Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить