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

Dijktra's 20C ?
Автор iamdumb, 9 лет назад, По-английски

Can anybody please help me with this question.I know how to calculate shortest path but I have no idea how to actually trace the nodes in the shortest path.What modification to naive dijktra's has be made?

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

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

When using JAVA, I'd create a class called Node, and have a String attribute for the path. Every node I enqueue in the priority queue, I'd the the node it's coming through + the previous path.

Maybe there is a better way, but that's how I do it.

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

Keep another array 'B', if you are currently in node 'v', when you want to update the shortest distance of a node 'u', write 'B[u]=v' , finally, to get the shortest path, start from the ending node, and go backwards in the array B until you reach the starting node : 


int len=0;  
int v=end_node;
while (1)
{
     path[len++]=v; 
     if (v==start_node)
         break; 
     v=B[v];
}

now you have the path (backwards)

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

    I applied your logic but i am not getting correct answer maybe anything wrong with concepts.Can you see this what it wrong with my implementation http://ideone.com/d47g3K

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

      Line 37, instead of

      if(!f[v] && d[s]+w<d[v])

      It should be

      if(d[s]+w<d[v])

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

        Sir,if you won't mind can I ask you the logic behind removing the !f[v].

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

          Im sorry, that wasn't the reason for the bug, this is:
          when you have a priority_queue of pairs, it will sort according to first element, then according to the second.
          So you should swap between first and second (first is length, second is node)
          AC Code : 11353425

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

What I did was maintain an array par[] and for each node,i, explored store its parent vertex in par[i]. Then to output shortest path, start from n and keep printing par[] values till par[i] is equal to start vertex.

→ Ответить