Dijkstra's shortest path algorithm

E1045595

graph algorithm shortest path algorithm single-source shortest path algorithm

Dijkstra's shortest path algorithm is a classic graph algorithm that efficiently computes the minimum-cost paths from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.

Try in SPARQL Jump to: Surface forms Disambiguation Statements Elicitation Referenced by

All labels observed (6)

Label	Occurrences
Dijkstra algorithm	1
Dijkstra shortest path first	1
Dijkstra shortest path first algorithm	1
Dijkstra shortest-path-first algorithm	1
Dijkstra's algorithm	1
Dijkstra's shortest path algorithm canonical	1

How this entity was disambiguated

This entity first appeared as the object of triple T13507193 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: Dijkstra's shortest path algorithm
Context triple: [Fibonacci heap, usedInAlgorithm, Dijkstra's shortest path algorithm]

A. Dijkstra
Dijkstra is a renowned Dutch computer scientist best known for his pioneering work in algorithms, including Dijkstra's shortest path algorithm, and for his influential contributions to programming methodology and software engineering.
B. Bellman–Ford algorithm
The Bellman–Ford algorithm is a graph shortest-path algorithm that can handle negative edge weights and detect negative cycles, often used in routing and network optimization.
C. Kruskal
Kruskal is a surname most prominently associated with American mathematician Martin David Kruskal, known for his work in soliton theory and nonlinear science.
D. Graph Algorithms (book)
"Graph Algorithms" is a foundational textbook by Shimon Even that systematically presents the theory, design, and analysis of algorithms for solving fundamental problems on graphs.
E. Tarjan's strongly connected components algorithm
Tarjan's strongly connected components algorithm is a classic linear-time graph algorithm that efficiently identifies all strongly connected components in a directed graph using depth-first search and low-link values.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: Dijkstra's shortest path algorithm
Target entity description: Dijkstra's shortest path algorithm is a classic graph algorithm that efficiently computes the minimum-cost paths from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.

A. Dijkstra
Dijkstra is a renowned Dutch computer scientist best known for his pioneering work in algorithms, including Dijkstra's shortest path algorithm, and for his influential contributions to programming methodology and software engineering.
B. Bellman–Ford algorithm
The Bellman–Ford algorithm is a graph shortest-path algorithm that can handle negative edge weights and detect negative cycles, often used in routing and network optimization.
C. Kruskal
Kruskal is a surname most prominently associated with American mathematician Martin David Kruskal, known for his work in soliton theory and nonlinear science.
D. Graph Algorithms (book)
"Graph Algorithms" is a foundational textbook by Shimon Even that systematically presents the theory, design, and analysis of algorithms for solving fundamental problems on graphs.
E. Tarjan's strongly connected components algorithm
Tarjan's strongly connected components algorithm is a classic linear-time graph algorithm that efficiently identifies all strongly connected components in a directed graph using depth-first search and low-link values.
F. None of above. chosen

Statements (51)

Predicate	Object
instanceOf	graph algorithm ⓘ shortest path algorithm ⓘ single-source shortest path algorithm ⓘ
algorithmParadigm	greedy algorithm ⓘ
application	GPS navigation systems ⓘ game AI pathfinding ⓘ robot path planning ⓘ routing in communication networks ⓘ transportation planning ⓘ
assumesEdgeWeights	non-negative ⓘ
correctFor	graphs with non-negative edge weights ⓘ
definedOn	weighted graph ⓘ
developedBy	Edsger W. Dijkstra ⓘ
failsWhen	graph has negative edge weights ⓘ graph has negative weight cycle ⓘ
field	computer science ⓘ
graphType	directed graph ⓘ undirected graph ⓘ
input	graph ⓘ source vertex ⓘ
namedAfter	Edsger W. Dijkstra ⓘ
notCorrectFor	graphs with negative edge weights ⓘ
output	shortest path distances from source to all vertices ⓘ shortest path tree ⓘ
property	computes optimal paths under non-negative weights ⓘ deterministic algorithm ⓘ label-setting algorithm ⓘ
relatedTo	A* search algorithm ⓘ linked to: A* search Bellman–Ford algorithm ⓘ Floyd–Warshall algorithm ⓘ Johnson's algorithm ⓘ linked to: Bellman–Ford algorithm
requires	non-negative edge weights ⓘ
solvesProblem	single-source shortest path problem ⓘ
spaceComplexity	O(V + E) ⓘ
step	initializes all distances to infinity except source ⓘ relaxes outgoing edges of selected vertex ⓘ repeatedly selects vertex with minimum tentative distance ⓘ
subfield	algorithms ⓘ graph theory ⓘ
terminatesWhen	all vertices are processed ⓘ
timeComplexity	O((V + E) log V) with binary heap ⓘ O(E + V log V) with Fibonacci heap ⓘ O(V^2) with adjacency matrix and simple array ⓘ
usesDataStructure	distance array ⓘ min-heap ⓘ predecessor array ⓘ priority queue ⓘ
worksOn	dense graphs ⓘ sparse graphs ⓘ
yearProposed	1956 ⓘ
yearPublished	1959 ⓘ

How these facts were elicited