Editing Dijkstra's algorithm (section)

===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, and insert new items as they are discovered (instead of doing a decrease-key, check whether the key is in the queue; if it is, decrease its key, otherwise insert it).{{r|mehlhorn}}{{rp|198}} This variant has the same worst-case bounds as the common variant, but maintains a smaller priority queue in practice, speeding up queue operations.<ref name="felner">{{cite conference |last=Felner |first=Ariel |year=2011 |title=Position Paper: Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm |url=http://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/view/4017/4357 |conference=Proc. 4th Int'l Symp. on Combinatorial Search |archive-url=https://web.archive.org/web/20200218150924/https://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/view/4017/4357 |archive-date=18 February 2020 |access-date=12 February 2015 |url-status=dead}} In a route-finding problem, Felner finds that the queue can be a factor 500–600 smaller, taking some 40% of the running time.</ref>

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{{r|felner}}<ref name="aima">{{Cite AIMA|3|pages=75, 81}}</ref><ref>Sometimes also ''least-cost-first search'': {{cite journal |last=Nau |first=Dana S. |year=1983 |title=Expert computer systems |url=https://www.cs.umd.edu/~nau/papers/nau1983expert.pdf |journal=Computer |publisher=IEEE |volume=16 |issue=2 |pages=63–85 |doi=10.1109/mc.1983.1654302 |s2cid=7301753}}</ref> and can be expressed in pseudocode as<!--NOTE TO EDITORS: Don't get confused by "uniform" in the name and remove costs from the pseudocode. UCS includes costs and is different from breadth-first search.-->
 '''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 {{math|''C''<sup>*</sup>}} is the length of the shortest path from the start node to any node satisfying the "goal" predicate, each edge has cost at least ''{{mvar|ε}}'', and the number of neighbors per node is bounded by ''{{mvar|b}}'', then the algorithm's worst-case time and space complexity are both in {{math|''O''(''b''<sup>1+⌊''C''<sup>*</sup> {{frac}} ''ε''⌋</sup>)}}.{{r|aima}}

Further optimizations for the single-target case include [[Bidirectional search|bidirectional]] variants, goal-directed variants such as the [[A* algorithm]] (see {{slink||Related problems and algorithms}}), 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 {{math|''s''–''t''}} routing to connecting ''{{mvar|s}}'' and ''{{mvar|t}}'' to their respective "[[Transit Node Routing|transit nodes]]" followed by shortest-path computation between these transit nodes using a "highway".<ref name="speedup2">{{cite conference |last1=Wagner |first1=Dorothea |last2=Willhalm |first2=Thomas |year=2007 |title=Speed-up techniques for shortest-path computations |conference=STACS |pages=23–36}}</ref> Combinations of such techniques may be needed for optimal practical performance on specific problems.<ref>{{cite journal |last1=Bauer |first1=Reinhard |last2=Delling |first2=Daniel |last3=Sanders |first3=Peter |last4=Schieferdecker |first4=Dennis |last5=Schultes |first5=Dominik |last6=Wagner |first6=Dorothea |year=2010 |title=Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm |url=https://publikationen.bibliothek.kit.edu/1000014952 |journal=J. Experimental Algorithmics |volume=15 |pages=2.1 |doi=10.1145/1671970.1671976 |s2cid=1661292}}</ref>