Home / Curated / Algorithms / Dijkstra shortest-path algorithm

Dijkstra shortest-path algorithm

Algorithms AIMech:DijkstraShortestPath DRAFT

Aliases: Dijkstra's algorithm, Dijkstra shortest path

A shortest-path algorithm for nonnegative edge weights that repeatedly settles the unsettled vertex with the smallest tentative distance from a source and relaxes its outgoing edges.

Identity Notes & Concept Scope The shortest-path method in Problem 2 of Dijkstra’s 1959 paper is curated here. Problem 1 in the same paper constructs a minimum spanning tree and is a distinct algorithm. A shortest-path tree need not be a minimum spanning tree; cost-prioritized search is distinct from breadth-first edge-count traversal and heuristic A-star search. No normalized identity match was found across the 442 AIO and 119 prior native records; ignored-inclusive text hits in the main checkout were dependency-package documentation and an unrelated package-metadata substring, not existing concept records.

Claims & Grounded Evidence

2 Claims

Mechanism #search-procedure

Maintain settled vertices and tentative source distances. A shorter route through the most recently settled vertex replaces a tentative distance and predecessor; the next vertex settled is the one with minimum tentative source distance. For a specified destination, the original method stops when that destination is settled.

supports Source: A Note on Two Problems in Connexion with Graphs · Locator: Problem 2, printed pp. 270–271 / PDF pp. 2–3, Steps 1–2 and Remarks 1–2; connected-graph setup on p. 269 / PDF p. 1

Scope #weights-and-output

The versioned implementation applies to directed or undirected graphs with nonnegative weights, maintains tentative labels in a minimum-priority queue, and returns source distances or predecessor data. Its shortest-path tree is not guaranteed to be a minimum spanning tree.

supports Source: Boost Graph Library: Dijkstra’s Shortest Paths · Locator: Algorithm description and DIJKSTRA pseudocode; weight_map, predecessor_map and distance_map parameters; Notes [1]

⚠️ Curated Limitations & Negative Results

Nonnegative edge weights are a precondition of the standard method; the record does not extend its settling rule to graphs with negative edges.
The 1959 presentation assumes a connected graph. The cited implementation documents source-unreachable vertices separately; reaching an arbitrary node does not establish a path to every node.
No particular heap implementation, asymptotic runtime, or universal advantage over other shortest-path algorithms is asserted.

Artificial Intelligence Ontology (AIO) Grounding

Explicit AIO Snapshot Assessment: No Match

Rationale: No suitable AIO counterpart for this graph/state-space search procedure was identified in the inspected snapshot. Using graphs, evaluation functions or a search subroutine in an AI system does not equate the algorithm with a learned model, a learning task or a mathematical function.

Search Scope: All 442 pinned AIO labels and scoped synonyms and 119 preceding native identities were compared. Both updated checkouts were searched including hidden and ignored files. Exact CLASS nodes and edges for GraphLanguageModel, ReasoningLLM, NeuroSymbolicLLM, MachineLearningTask, MathematicalFunction and ReinforcementLearning were inspected, alongside semantic search for search, planning, heuristic, path, traversal, symbolic, reasoning and graph terminology.

Examined AIO Candidate	Rejection Reason
`AIO:GraphLanguageModel`	A language model operating on structured graph representations is not a graph traversal or shortest-path algorithm.
`AIO:ReasoningLLM`	Language-task deductive inference does not denote general state-space search.
`AIO:NeuroSymbolicLLM`	A language-model architecture combining neural and symbolic components is not the search procedure itself.
`AIO:MachineLearningTask`	Building methods that learn from data is not the identity of an algorithm traversing a specified graph.
`AIO:MathematicalFunction`	The search procedure is distinct from the mathematical functions it may evaluate.
`AIO:ReinforcementLearning`	A learning task balancing exploration and exploitation is distinct from deterministic graph/state-space traversal.

Evidence Sources & Primary Literature

2 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`method-source`	A Note on Two Problems in Connexion with Graphs Edsger W. Dijkstra	primary paper full_text	ID: doi:10.1007/BF01386390 sha256:baa66780e853…
`versioned-documentation`	Boost Graph Library: Dijkstra’s Shortest Paths Jeremy Siek	official documentation documentation	sha256:3bcfc6120324…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-11T05:32:15Z

Updated: 2026-10-11T05:32:31Z

Source File: data/curated/DijkstraShortestPath.yaml