graph algorithms fibonacci heap when this is usedthe running time is (| |+|vlog | |fibonacci heaps have good theoretical time bounds but fair amount of overheadso it is not clear whether using fibonacci heaps is actually better in practice than dijkstra' algorithm with binary heaps to datethere are no meaningful average-case results for this problem graphs with negative edge costs if the graph has negative edge coststhen dijkstra' algorithm does not work the problem is that once vertexuis declared knownit is possible that from some other unknown vertexvthere is path back to that is very negative in such casetaking path from to back to is better than going from to without using exercise (aasks you to construct an explicit example tempting solution is to add constant to each edge costthus removing negative edgescalculate shortest path on the new graphand then use that result on the original the naive implementation of this strategy does not work because paths with many edges become more weighty than paths with few edges combination of the weighted and unweighted algorithms will solve the problembut at the cost of drastic increase in running time we forget about the concept of known verticessince our algorithm needs to be able to change its mind we begin by placing on queue thenat each stagewe dequeue vertex we find all vertices adjacent to such that dw dv cv, we update dw and pw and place on queue if it is not already there bit can be set for each vertex to indicate presence in the queue we repeat the process until the queue is empty figure (almostimplements this algorithm although the algorithm works if there are no negative-cost cyclesit is no longer true that the code in the inner for loop is executed once per edge each vertex can dequeue at most |vtimesso the running time is (| | |if adjacency lists are used (exercise ( )this is quite an increase from dijkstra' algorithmso it is fortunate thatin practiceedge costs are nonnegative if negative-cost cycles are presentthen the algorithm as written will loop indefinitely by stopping the algorithm after any vertex has dequeued | timeswe can guarantee termination acyclic graphs if the graph is known to be acyclicwe can improve dijkstra' algorithm by changing the order in which vertices are declared knownotherwise known as the vertex selection rule the new rule is to select vertices in topological order the algorithm can be done in one passsince the selections and updates can take place as the topological sort is being performed this selection rule works because when vertex is selectedits distancedv can no longer be loweredsince by the topological ordering rule it has no incoming edges emanating from unknown nodes there is no need for priority queue with this selection rulethe running time is (| | |)since the selection takes constant time an acyclic graph could model some downhill skiing problem--we want to get from point to bbut can only go downhillso clearly there are no cycles another possible