Hi Everybody,
There is a question regarding the implementation of dijkstra's shortest path
routing algorithm is ns2 (dijkstra.cc file). The code begins with two set of
nodes: Q and S. Initially the set Q contains all the nodes of the graph
while the set S is empty. Now a node is moved from Q to S, one at a time,
if it has the shortest distance from the source node among all the nodes in
Q.
I have gone through the code and but dont see any line(s) where a node from
Q is choosen to be moved into S.
Q_it u = Q.begin(); // Smallest line 67
if(0)printf("Smallest is node %ld dist %ld\n", u->second,
u->first); line 68
S.insert(QPair_t(u->first, u->second)); // Add to S for later
printout line 69
Does that mean that u points to a node in Q which is at shortest distance
to source node, among all the nodes in Q ? because that is the node being
moved into S (at line 69)...........and if this happens to be the case, than
what about the case when we have more than one node in Q which are
equidistant from the root node...........I mean which node is choosen first
to be moved into S ?
Thanks!
Piyush
