Dijkstra's algorithm

Dijkstra's algorithm is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for finding the <a href="/facts/Shortest_path_problem/g4nsrswr">shortest paths</a> between <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">nodes</a> in a weighted <a href="/facts/Graph_(abstract_data_type)/b8qcddXa">graph</a>, which may represent, for example, a <a href="/facts/Road_network/6vk6zHBE">road network</a>. It was conceived by <a href="/facts/Computer_scientist/DavggjGL">computer scientist</a> <a href="/facts/Edsger_W._Dijkstra/910x0MjT">Edsger W. Dijkstra</a> in 1956 and published three years later.
Dijkstra's algorithm finds the shortest path from a given source node to every other node.: 196–206  It can be used to find the shortest path to a specific destination node, by terminating the algorithm after determining the shortest path to the destination node. For example, if the nodes of the graph represent cities, and the costs of edges represent the distances between pairs of cities connected by a direct road, then Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. A common application of shortest path algorithms is network <a href="/facts/Routing_protocol/LH5U2Qh5">routing protocols</a>, most notably <a href="/facts/IS-IS/zaNkSwhW">IS-IS</a> (Intermediate System to Intermediate System) and <a href="/facts/Open_Shortest_Path_First/PACpGUHb">OSPF</a> (Open Shortest Path First). It is also employed as a <a href="/facts/Subroutine/9vFJrg0A">subroutine</a> in algorithms such as <a href="/facts/Johnson%2527s_algorithm/ef7m9e3n">Johnson's algorithm</a>.
The algorithm uses a <a href="/facts/Priority_queue/1uXVo4Uf">min-priority queue</a> data structure for selecting the shortest paths known so far. Before more advanced priority queue structures were discovered, Dijkstra's original algorithm ran in 
 
 
 
 Θ
 (
 
 |
 
 V
 
 
 |
 
 
 2
 
 
 )
 
 
 {\displaystyle \Theta (|V|^{2})}
 
 <a href="/facts/Time_complexity/77T62gmf">time</a>, where 
 
 
 
 
 |
 
 V
 
 |
 
 
 
 {\displaystyle |V|}
 
 is the number of nodes. Fredman & Tarjan 1984 proposed a <a href="/facts/Fibonacci_heap/4cJIHkNQ">Fibonacci heap</a> priority queue to optimize the running time complexity to 
 
 
 
 Θ
 (
 
 |
 
 E
 
 |
 
 +
 
 |
 
 V
 
 |
 
 log
 ⁡
 
 |
 
 V
 
 |
 
 )
 
 
 {\displaystyle \Theta (|E|+|V|\log |V|)}
 
. This is <a href="/facts/Asymptotic_computational_complexity/fMuA7mEP">asymptotically</a> the fastest known single-source <a href="/facts/Shortest_path_problem/g4nsrswr">shortest-path algorithm</a> for arbitrary <a href="/facts/Directed_graph/YBdfQ0um">directed graphs</a> with unbounded non-negative weights. However, specialized cases (such as bounded/integer weights, directed acyclic graphs etc.) can be improved further. If preprocessing is allowed, algorithms such as <a href="/facts/Contraction_hierarchy/fCbJ5FIP">contraction hierarchies</a> can be up to seven orders of magnitude faster.
Dijkstra's algorithm is commonly used on graphs where the edge weights are positive integers or real numbers. It can be generalized to any graph where the edge weights are <a href="/facts/Partially_ordered_set/qb4a3FAX">partially ordered</a>, provided the subsequent labels (a subsequent label is produced when traversing an edge) are <a href="/facts/Monotonic_function/MjQK0YL2">monotonically</a> non-decreasing.
In many fields, particularly <a href="/facts/Artificial_intelligence/lJGauQwX">artificial intelligence</a>, Dijkstra's algorithm or a variant offers a uniform cost search and is formulated as an instance of the more general idea of <a href="/facts/Best-first_search/jaIwMxBE">best-first search</a>.

Dijkstra's algorithm open-in-new

Dijkstra's algorithm