Can someone tell me why almost in every book/website/paper authors use the following:
foreach vertex v in Adjacent(u) relax(u,v)
when relaxing the edges, instead of:
foreach vertex v in Adjacent(u) if (v is in Q) relax(u,v)
This is extremely confusing for someone when learning the algorithm. Is there any reason why the people are omitting the IF ?
while (queue.length != 0) min = queue.getMinAndRemoveItFromQ() foreach v in min.adjacentVertices // inspect edge from "min" to "v" if ( queue.contains(v) AND min.priority + weight(min,v) < v.priority ) v.priority = min.priority + weight(min,v) v.pre = min
Is this implementation correct or am I missing something ?