iamdumb's blog

Dijktra's 20C ?
By iamdumb, 10 years ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

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

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)

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

    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

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

      Line 37, instead of

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

      It should be

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

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

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

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

          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

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

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.

→ Reply