figure bad case for unweighted shortest-path algorithm using figure by tracing back through the pv variablethe actual path can be printed we will see how when we discuss the weighted case the running time of the algorithm is (| | )because of the doubly nested for loops an obvious inefficiency is that the outside loop continues until num_vertices- even if all the vertices become known much earlier although an extra test could be made to avoid thisit does not affect the worst-case running timeas can be seen by generalizing what happens when the input is the graph in figure with start vertex we can remove the inefficiency in much the same way as was done for topological sort at any point in timethere are only two types of unknown vertices that have dv some have dv currdistand the rest have dv currdist because of this extra structureit is very wasteful to search through the entire table to find proper vertex very simple but abstract solution is to keep two boxes box # will have the unknown vertices with dv currdistand box # will have dv currdist the test to find an appropriate vertex can be replaced by finding any vertex in box # after updating (inside the innermost if block)we can add to box # after the outermost for loop terminatesbox # is emptyand box # can be transferred to box # for the next pass of the for loop we can refine this idea even further by using just one queue at the start of the passthe queue contains only vertices of distance currdist when we add adjacent vertices of distance currdist since they enqueue at the rearwe are guaranteed that they will not be processed until after all the vertices of distance currdist have been processed after the last vertex at distance currdist dequeues and is processedthe queue only contains vertices of distance currdist so this process perpetuates we merely need to begin the process by placing the start node on the queue by itself the refined algorithm is shown in figure in the pseudocodewe have assumed that the start vertexsis passed as parameter alsoit is possible that the queue might empty prematurelyif some vertices are unreachable from the start node in this casea distance of infinity will be reported for these nodeswhich is perfectly reasonable finallythe known data member is not usedonce vertex is processed it can never enter the queue againso the fact that it need not be reprocessed is implicitly marked thusthe known data member can be discarded figure shows how the values on the graph we have been using are changed during the algorithm (it includes the changes that would occur to known if we had kept itusing the same analysis as was performed for topological sortwe see that the running time is (| | |)as long as adjacency lists are used dijkstra' algorithm if the graph is weightedthe problem (apparentlybecomes harderbut we can still use the ideas from the unweighted case