shorter path using we would have updated it when processing . After all nodes are visited, the shortest path from to any node consists only of visited nodes, therefore is the shortest distance. Running time Bounds of the running time of Dijkstra's algorithm on a graph with edges and vertices can be expressed as a function of the number of edges, denoted , and the number of vertices, denoted , using big-O notation. The complexity bound depends mainly on the data structure used to represent the set . In the following, upper bounds can be simplified because is for any graph, but that simplification disregards the fact that in some problems, other upper bounds on may hold. For any data structure for the vertex set , the running time is in where and are the complexities of the decrease-key and extract-minimum operations in , respectively. The simplest version of Dijkstra's algorithm stores the vertex set as an linked list or array, and edges as an adjacency list or matrix. In this case, extract-minimum is simply a linear search through all vertices in , so the running time is . For sparse graphs, that is, graphs with far fewer than edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using a self-balancing binary search tree, binary heap, pairing heap, or Fibonacci heap as a priority queue to implement extracting minimum efficiently. To perform decrease-key steps in a binary heap efficiently, it is necessary to use an auxiliary data structure that maps each vertex to its position in the heap, and to keep this structure up to date as the priority queue changes. With a self-balancing binary search tree or binary heap, the algorithm requires time in the worst case (where denotes the binary logarithm ); for connected graphs this time bound can be simplified to . The Fibonacci heap improves this to When using binary heaps, the average case time complexity is lower than the worst-case: assuming edge costs are drawn independently from a common probability distribution, the expected number of decrease-key operations is bounded by , giving a total running time of Practical optimizations and infinite graphs In common presentations of Dijkstra's algorithm, initially all nodes are entered into the priority queue. This is, however, not necessary: the algorithm can start with a priority queue that contains only one item,