The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index; none of the 3 sources its claims cite is checked for support yet.
A Note on Dijkstra's Shortest Path Algorithm
Open accessAbstract
An assertion that Dijkstra's algorithm for shortest paths (adapted to allow arcs of negative weight) runs in O ( n 3 ) steps is disproved by showing a set of networks which take O ( n 2 n ) steps.
Overview
CoChat Summary
TL;DR
Johnson disproves the claim that a modified Dijkstra algorithm allowing negative arcs runs in \(O(n^2)\) steps by constructing networks with no negative cycles on which it takes exponential time. The paper proves a family \(D_n\) requiring \((n-1)2^{n-1}\) steps, stated as \(O(n2^n)\).
Key findings
- The modified Dijkstra algorithm—allowing a node to re-enter \(S\) when its distance decreases—can take exponential time on general networks; there exist networks \(D_n\) for all \(n \ge 2\), with no directed cycles of negative weight, on which it runs \(O(n2^n)\) steps.
- For the related network \(D'_n\) (with \(p_n = +\infty\)), the algorithm has exactly \(2^{n-1}\) admissions of nodes to \(S\).
- The proof counts step 4 executed once per admitted node, with \(n-1\) arcs explored each time, giving \((n-1)2^{n-1}\) steps, which is \(O(n2^n)\).
- The paper notes the modified algorithm still runs in \(O(n^2)\) steps when there are no negative-weight arcs, but can be a poor choice in the general case.
Methods
- Theoretical proof by construction and induction. The modified algorithm is defined by allowing a node to enter \(S\) more than once if its distance label decreases; otherwise it matches the original algorithm.
- A family of networks \(D_n\) is defined with \(n^2 - n\) arcs and specified weights, and shown to have no negative-weight directed cycles. A related network \(D'_n\) with \(p_n = +\infty\) is used to simplify the induction.
- A lemma about sequences of states of \(S\) and admissions to \(S\) is proved, then used to count admissions and arc explorations, yielding the running-time bound.
Limitations
- Stated: the paper does not prove that \(D_n\) is “worst” in the sense that no network takes more operations to terminate, although it asserts this as a fact.
- Stated: \(D'_n\) is artificial because it has infinite-weight arcs that can be eliminated; the resulting incomplete network is no longer a “worst” network, and a precise order is harder to prove.
- Evident: the result is a theoretical worst-case construction for the modified Dijkstra algorithm; no empirical benchmarks or implementation data are presented.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
0 Valid · 1 Not valid · 3 Not checked · 16 Own results and interpretations
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“When p. = 2” there are no negative weight cycles since”
§ A Note on Dijkstra's Shortest Path Algorithm > Abstract
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Any directed cycle of D. can have at most n --1 arcs of negative weight since there must be at least one arc of weight p~ to complete any cycle.”
§ A Note on Dijkstra's Shortest Path Algorithm > Abstract
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“THEOREM.There exists a network D, for all n >_ 2 and with no directed cycles of negative weight, on whwh the modified Dijkstra's algorithm runs for O( n2”) steps.”
- Also stated in: § Abstract · boosted
“An assertion that Dljkstra'a algorithm for shortest paths (adapted to allow arcs of negative weight) runs m 0 (n a) steps is disproved by showing a set of networks which take 0 (n2 ”) steps.”
§ A Note on Dijkstra's Shortest Path Algorithm > Abstract
boostedstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Also stated in: § Abstract · boosted
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“This network has the property that the weights A(v,, v~) for any D~' are identical to the weights for D.', n > m, over the node indices i, j < m.”
§ A Note on Dijkstra's Shortest Path Algorithm > Abstract
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Therefore max,.~([ ~(v,) -a(v~) [) is nondecreasing over the execution of the algorithm”
§ A Note on Dijkstra's Shortest Path Algorithm > ~(v.) -1.
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
4 more claims
Create a free account to see all 20 claims and every source verdict.
- It may state two separate claims as one. 9
- The quote only partly states this claim. 1
- Probably not a substantial claim. 3
Citations
Cites
A note on two problems in connexion with graphs
Dijkstra, E. W. (1959) · Numerische Mathematik · doi:10.1007/bf01386390 · Cited by 29,065
Floyd, R. W. (1962) · Communications of the ACM · doi:10.1145/367766.368168 · Cited by 3,998
Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
Edmonds, J., & Karp, R. M. (1972) · Journal of the ACM · doi:10.1145/321694.321699 · Cited by 2,528
Cited by
Efficient Algorithms for Shortest Paths in Sparse Networks
Johnson, D. B. (1977) · Journal of the ACM · doi:10.1145/321992.321993 · Cited by 1,041
Self-citationGallo, G., & Pallottino, S. (1988) · Annals of Operations Research · doi:10.1007/bf02288320 · Cited by 352
Shortest‐path algorithms: Taxonomy and annotation
Deo, N., & Pang, C. (1984) · Networks · doi:10.1002/net.3230140208 · Cited by 309
Indoor positioning and wayfinding systems: a survey
Kunhoth, J., Karkar, A., Al-Maadeed, S., & Al-Ali, A. (2020) · Human-centric Computing and Information Sciences · doi:10.1186/s13673-020-00222-0 · Cited by 270
Shortest Path Algorithms In Transportation Models: Classical and Innovative Aspects
Pallottino, S., & Scutellà, M. G. (1998) · Equilibrium and Advanced Transportation Modelling · doi:10.1007/978-1-4615-5757-9_11 · Cited by 267
Metadata
- Authors
- Johnson, D. B.
- Affiliations
- Cornell University (US)
- Corresponding author
- Johnson, Donald B.
- Venue
- Journal of the ACM
- Published
- 1973-07
- Volume
- 20
- Issue
- 3
- Pages
- 385-388
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2092330486
- Semantic Scholar
- d7d2bbfd94ccc6292781cc110e111ccb23fd7d11
- Cited by
- 380
- References
- 3
- Citations by year
- 2026: 13 · 2025: 21 · 2024: 30 · 2023: 30 · 2022: 36 · 2021: 34 · 2020: 34 · 2019: 19 · 2018: 27 · 2017: 10 · 2016: 13 · 2015: 14 · 2014: 10 · 2013: 10 · 2012: 6
- FWCI
- 0.48
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Journal of the ACM (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Keywords
- Dijkstra's algorithm, shortest path, negative edge weights, time complexity, computational complexity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
A language model drew the claims from the paper on 2026-11-17, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-11-17 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: A Note on Dijkstra's Shortest Path Algorithm. https://app.cochat.ai/papers/10.1145/321765.321768
- The paper
- Johnson, D. B. (1973). A Note on Dijkstra's Shortest Path Algorithm. Journal of the ACM. https://doi.org/10.1145/321765.321768
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.