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 |E| is O(|V|^2) for any simple graph, but that simplification disregards the fact that in some problems, other upper bounds on |E| may hold. For any data structure for the vertex set the running time is: {{block indent|\Theta(|E| \cdot T_\mathrm{dk} + |V| \cdot T_\mathrm{em}),}} where T_\mathrm{dk} and T_\mathrm{em} 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 a 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 \Theta(|E| + |V|^2) = \Theta(|V|^2). For
sparse graphs, that is, graphs with far fewer than |V|^2 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,
Fibonacci heap or a priority 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 update this structure as the priority queue changes. With a self-balancing binary search tree or binary heap, the algorithm requires \Theta((|E| + |V|) \log |V|) time in the worst case; for connected graphs this time bound can be simplified to \Theta( | E | \log | V | ). The
Fibonacci heap improves this to \Theta(|E| + |V| \log|V|). 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 \Theta(|V| \log (|E|/|V|)), giving a total running time of Moreover, not inserting all nodes in a graph makes it possible to extend the algorithm to find the shortest path from a single source to the closest of a set of target nodes on infinite graphs or those too large to represent in memory. The resulting algorithm is called
uniform-cost search (UCS) in the artificial intelligence literature and can be expressed in pseudocode as
procedure uniform_cost_search(start)
is node ← start frontier ← priority queue containing node only expanded ← empty set
do if frontier is empty
then return failure node ← frontier.pop()
if node is a goal state
then return solution(node) expanded.add(node)
for each of node's neighbors
n do if n is not in expanded and not in frontier
then frontier.add(
n)
else if n is in frontier with higher cost replace existing node with
n Its complexity can be expressed in an alternative way for very large graphs: when is the length of the shortest path from the start node to any node satisfying the "goal" predicate, each edge has cost at least , and the number of neighbors per node is bounded by , then the algorithm's worst-case time and space complexity are both in . Further optimizations for the single-target case include
bidirectional variants, goal-directed variants such as the
A* algorithm (see ), graph pruning to determine which nodes are likely to form the middle segment of shortest paths (reach-based routing), and hierarchical decompositions of the input graph that reduce routing to connecting and to their respective "
transit nodes" followed by shortest-path computation between these transit nodes using a "highway". Combinations of such techniques may be needed for optimal practical performance on specific problems.
Bidirectional Dijkstra Bidirectional Dijkstra is a variant of Dijkstra's algorithm designed to efficiently compute the shortest path between a given source vertex and target vertex , rather than all vertices. The key idea is to run two simultaneous searches: one forward from on the original graph and one backward from on the graph with edges reversed. Each search maintains its own tentative distance estimates, priority queue, and set of "settled" vertices. The two frontiers advance toward each other and meet somewhere along the shortest path. Two distance arrays are maintained: (distance from to ) and (distance from to ), initialized to except and . Two priority queues and hold vertices not yet fully processed, and two sets and store vertices whose shortest-path distance is finalized in each direction. A variable stores the length of the best full path found so far, initially . The algorithm repeatedly extracts the minimum-distance vertex from whichever queue currently has the smaller key, relaxes its outgoing (or incoming) edges, and updates whenever it discovers a connection between the two settled sets: and symmetrically for the backward search. A key feature is the stopping condition: once the sum of the current minimum priorities in both queues is at least , no yet-unsettled path can improve upon . At this point equals the true shortest-path distance , and the search terminates. If the actual shortest path (not just its distance) is desired, predecessor pointers can be stored in both searches. When μ is updated through some crossing vertex , the algorithm records this meeting point and reconstructs the final route as the forward path from to concatenated with the backward path from to . Theoretical research shows that an optimized bidirectional approach can be instance-optimal, meaning no correct algorithm can asymptotically relax fewer edges on the same graph instance.
Practical performance considerations Although Dijkstra's algorithm is optimal for graphs with non-negative edge weights, its practical runtime depends on both data structures and graph properties. Using a binary heap results in a running time of O((V+E)logV). Alternatives such as Fibonacci heaps provide better theoretical bounds but often perform worse in real applications because of large constant factors. Graph structure also plays a major role. Sparse networks, such as road maps, allow Dijkstra's algorithm to operate efficiently since most vertices have low degree. Dense graphs increase relaxations and slow down the process. Because of this, modern routing systems often use Dijkstra's algorithm together with preprocessing methods such as A* search, landmark heuristics, or contraction hierarchies, which significantly reduce the search space. Memory locality is another important factor. Cache-optimized priority queues and adjacency layouts can reduce latency for large graphs that exceed CPU cache limitations. Because of these considerations, most real-world systems use specialized Dijkstra variants tuned for specific graph families and hardware constraints.
Optimality for comparison-sorting by distance As well as simply computing distances and paths, Dijkstra's algorithm can be used to sort vertices by their distances from a given starting vertex. In 2023, Haeupler, Rozhoň, Tětek, Hladík, and
Tarjan (one of the inventors of the 1984 heap), proved that, for this sorting problem on a positively-weighted directed graph, a version of Dijkstra's algorithm with a special heap data structure has a runtime and number of comparisons that is within a constant factor of optimal among
comparison-based algorithms for the same sorting problem on the same graph and starting vertex but with variable edge weights. To achieve this, they use a comparison-based heap whose cost of returning/removing the minimum element from the heap is logarithmic in the number of elements inserted after it rather than in the number of elements in the heap.
Specialized variants When arc weights are small integers (bounded by a parameter C), specialized queues can be used for increased speed. The first algorithm of this type was Dial's algorithm for graphs with positive integer edge weights, which uses a
bucket queue to obtain a running time The use of a
Van Emde Boas tree as the priority queue brings the complexity to Another interesting variant based on a combination of a new
radix heap and the well-known Fibonacci heap runs in time {{nowrap|O(|E|+|V|\sqrt{\log C}).}} Finally, the best algorithms in this special case run in O(|E|\log\log|V|) time and O(|E| + |V|\min\{(\log|V|)^{1/3+\varepsilon}, (\log C)^{1/4+\varepsilon}\}) time. == Related problems and algorithms ==