Papalocal
Loading…
Papalocal · Things
Work

Dijkstra's algorithm

Dijkstra's algorithm is a graph search algorithm. It is based on breadth-first search.

All 5 facts, and where they come from

Facts

5 facts · 0 confirmed by two sources · 0 cited · 5 from one source

What it is
pathfinding algorithm One source
graph algorithm One source
greedy algorithm One source
Based on
breadth-first search One source
Named after

Where this comes from

Papalocal keeps its own record. It started from these sources; what each one said is kept here as it was copied, so a change on their side never changes this page by itself. Tap one to read its version.

What Wikidata says · copied November 17, 2026 · revision 2548044712
Described as
graph search algorithm
Other names
Dijkstra algorithm
What it is
pathfinding algorithm · 1 reference; graph algorithm · 1 reference; greedy algorithm · 1 reference
Based on
breadth-first search
Named after
Edsger W. Dijkstra
Wikipedias with a page
55

Wikidata item Q8548 (wikidata.org/wiki/Q8548), public domain (CC0). Copied 2026-11-17.

What Wikipedia says · copied November 17, 2026 · revision 1386096330

Dijkstra's algorithm (, DYKE-strəz) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, a road network. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
Dijkstra's algorithm finds the shortest path from a given source node to every other node. It can be used to find the shortest path to a specific destination node, by terminating the algorithm after determining the shortest path to that 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 routing protocols, most notably IS-IS (Intermediate System to Intermediate System) and OSPF (Open Shortest Path First). It is also employed as a subroutine in algorithms such as Johnson's algorithm.
The algorithm uses a min-priority queue 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) time, where |V| is the number of nodes. Fredman & Tarjan 1984 proposed a Fibonacci heap priority queue to optimize the running time complexity to Θ(|E|+|V|log⁡|V|), where |E| is the number of edges. This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs 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 contraction hierarchies can be up to seven orders of magnitude faster.
Dijkstra's algorithm is commonly used on graphs where the edge weights are non-negative integers or real numbers. It can be generalized to any graph where the edge weights are partially ordered, provided the subsequent labels (a subsequent label is produced when traversing an edge) are monotonically non-decreasing. In many fields, particularly artificial intelligence, Dijkstra's algorithm or a variant offers a uniform cost search and is formulated as an instance of the more general idea of best-first search.

From the Wikipedia article “Dijkstra's algorithm” (en.wikipedia.org/wiki/Dijkstra's_algorithm), by its contributors, under CC BY-SA 4.0 (creativecommons.org/licenses/by-sa/4.0/). Copied 2026-11-17; not changed.

Confirmed Two sources agree. Cited One source, and it names where it got it. One source One source, without a reference of its own. Sources disagree The sources disagree. We show the best-supported value and keep theirs below.

Picture: Ibmua, via Wikimedia Commons · Public domain

People connected 1

Known for it