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). This variant has the same worst-case bounds as the common variant, but maintains a smaller priority queue in practice, speeding up the queue operations. 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 The complexity of this algorithm 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 of Dijkstra's algorithm 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. Specialized variants When arc weights are small integers (bounded by a parameter ), specialized queues which take advantage of this fact can be used to speed up Dijkstra's algorithm. 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