A Note on Two Problems in Connexion with Graphs.

Dijkstra, E. W. (1959). A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1(1), 269-271.

Type

Journal article

Intellectual base

Primary research

Year

1959

Volume

1

Issue

1

Pages

269-271

DOI

10.1007/bf01386390

DOI registrant

Springer Nature

Link

https://doi.org/10.1007/BF01386390

Cited from

computer_science, mathematics, operations_research

Cited by

7 citations across 7 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Algorithm
  • Every element of algorithmic structure is present, and the algorithm is independent of any particular programming language or machine architecture

    This sourceOriginal presentation of the shortest-path algorithm — a finite, definite procedure with provable correctness on graphs with non-negative edge weights.

• Dynamic Programming
  • Held-Karp's algorithm (1962) and Dijkstra's shortest-path method (1959) exemplify the computational leverage of DP-based formulations.

    This sourceFoundational single-source shortest-path algorithm

• Network Flow Models
  • Listed in the references but not attached to a specific claim.
• Path
  • The algorithm constructs the ordered edge sequence by repeatedly extracting the nearest unsettled node and relaxing its outgoing edges, so the traversal invariant — every step honours a real adjacency — is maintained by construction.

Mechanisms

• Graph Shortest-Path Metric
  • The team builds a graph — intersections as nodes, road segments as edges weighted by expected travel time including turn and traffic penalties — and defines the distance between two addresses as the shortest-time path through it, computed with a standard shortest-path algorithm

    This sourceFormulates weighted-graph distance as the minimum-total-weight path and supplies a standard shortest-path algorithm.

• Priority-Queue Step Selection
  • Committing the popped best as settled is only safe when a settled candidate can never be improved by a later step — when the keys are monotone or consistent.

    This sourceShows that with positive branch lengths, selecting the currently shortest tentative path makes that path assignment final because later extensions cannot improve it.

• Route-Finding and Topology Search
  • Classical shortest-path search

    This sourceFormulates a graph algorithm for finding the minimum-total-length path between two nodes.

Verification

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Not recorded. Neither this nor any other of the 7 citations of this work carries a recorded support check.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

Registry ID ref:957992efa36a · see in the full table