Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat

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 access
Johnson, Donald B. · 1973 · Journal of the ACM

Abstract

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

Crossref · 10.1145/321765.321768

Cites

3 of 3 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

0 Valid · 1 Not valid · 3 Not checked · 16 Own results and interpretations

4 more claims

Create a free account to see all 20 claims and every source verdict.

See all claims — free account
  • It may state two separate claims as one. 9
  • The quote only partly states this claim. 1
  • Probably not a substantial claim. 3

Create a free account to see these claims.

Citations

Cites

Show all 3 references

Cited by

See all 380

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
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
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.