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

DOI

10.1007/bf01386390

Link

https://doi.org/10.1007/BF01386390

Cited from

computer_science, mathematics, operations_research

Cited by

4 citations across 4 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.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

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