iamdumb's blog

Dijktra's 20C ?
By iamdumb, 11 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?
»
11 years ago, hide # |
← 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
»
11 years ago, hide # |
← 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
»
11 years ago, hide # |
 
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