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
Items 301–380 of 380
Interval modulated target sensing in energy restraint wireless sensor networks
Wang, X., Wang, Y., & Sun, X. (2010) · Conference proceedings - IEEE Instrumentation/Measurement Technology Conference · doi:10.1109/imtc.2010.5488193 · Cited by 1
An Analysis of Choice in Program Design
Backhouse, R. (1983) · Springer eBooks · doi:10.1007/978-94-009-7019-9_3 · Cited by 1
Efficient data delivery in 5G mobile communication networks
Li, Y. (2019) · DepositOnce · doi:10.14279/depositonce-8245 · Cited by 1
SD-FFR: Software Defined Fast Failure Recovery Mechanism in the Automatic WarehousePreprint
Bai, T.-C., & Huang, C.-Y. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.02040 · Cited by 1
Thulasiraman, K., & Swamy, M. N. S. (1992) · Wiley eBooks · doi:10.1002/9781118033104.ch11 · Cited by 1
Dynamic Resource Provisioning and Survivability Strategies in Optical Networks
Ahmed, J. (2013) · KTH Publication Database DiVA (KTH Royal Institute of Technology) · Cited by 1
Sondak, R. C. (2010) · Research Repository (Delft University of Technology) · Cited by 1
Wong, T. (1999) · PolyPublie (École Polytechnique de Montréal) · Cited by 1
Elkael, M. (2023) · theses.fr (ABES) · doi:10.70675/ed88950dz2d9bz4a44zb11bzc5bbb7c50baa · Cited by 1
InferType: A Compiler Toolkit for Implementing Efficient Constraint-Based Type Inference
Li, S., Yamazaki, T., & Chiba, S. (2024) · Schloss Dagstuhl – Leibniz-Zentrum für Informatik · doi:10.4230/lipics.ecoop.2024.23
On Resilience Challenges in Opportunistic Networks
Mehrparvar, M. (2012) · DiVA (Digitala Vetenskapliga Arkivet)
Intermodality and substitution of modes for freight TransportationPreprint
Jourquin, B., Beuthe, M., & Ha, C. K. A. N. (1999) · RePEc: Research Papers in Economics
Sparse Key Points Controlled Animation for Individual Face Model
Yao, J., Wang, Y., & Ding, B. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-69736-7_65
Heuristic Approaches to Service Level Agreements in Packet Networks
Yu, L. L., Manning, E. G., & Li, K. F. (2005) · Lecture notes in computer science · doi:10.1007/11600930_101
Data dissemination in partially cooperative opportunistic networks
Greede, A. (2013) · ORCA Online Research @Cardiff (Cardiff University)
The Impact of Dynamic Network Effects and Decision Heuristics on Social Dynamics
Mungovan, D. (2011) · Arrow@dit (Dublin Institute of Technology) · doi:10.13025/16676
Incremental computation of shortest paths in semi-dynamic graphs using software components
Yasmin, N. (2006) · ACM Southeast Regional Conference (ACMSE) · doi:10.1145/1185448.1185470
Label diffusion on graph for face identification
Buyssens, P., & Revenu, M. (2012) · International Conference on Biometrics · doi:10.1109/icb.2012.6199757
A COVERING PROJECTION FOR ROBOT NAVIGATION UNDER STRONG ANISOTROPY
ANGHINOLFI, A., COSTA, L., Ferri, M., & Viarani, E. (2010) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195910003414
Dynamic Tree Switching for IP Networks
Neophytou, C. (2007) · OpenGrey (Institut de l'Information Scientifique et Technique)
Song, X. (2014) · doi:10.7282/t3w0948t
Path vs. destination: A case study of blind noise assessment using modified ant shortest path
Huang, X., Chen, L., & Tian, J. (2015) · Proceedings - International Conference on Image Processing · doi:10.1109/icip.2015.7351591
Event detection in interaction network
Xiao, H. (2016) · Työväentutkimus Vuosikirja
Building and validating gene regulatory networks (GRN) with delays from multiple data sources
Liu, W. (2015) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/65383
Service-Oriented Workflow Executability from a Security Perspective
Hussain, S., Sinnott, R., & POET, R. R. W. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-49148-6_30
Routing and Disaster Awareness in Optical Networks
Muhammad Iqbal, M. A. F. (2016) · Research Repository (Delft University of Technology) · doi:10.4233/uuid:64cd0a44-acc7-49bc-905a-017c4855511a
Um método biobjetivo de alocação de tráfego para veículos convencionais e elétricos
de Souza, M. (2015) · Americanae (AECID Library)
Le calcul parallèle des plus courts chemins temporels
Pépin, J.-N. (2003) · doi:10.71781/10712
Effective Fusion of Disaster-Relief Agent in RoboCupRescue Simulation
Kusaka, T., Miyamoto, Y., Hasegawa, A., Takami, S., Iwata, K., & Ito, N. (2018) · International Conference on Computational Science/Intelligence and Applied Informatics (CSII) · doi:10.1109/csii.2018.00021
Black Networks in Smart Cities
Chakrabarty, S. (2018) · SMU Scholar (Southern Methodist University)
Bhattacharjee, R., & De, A. (2018) · IEEE Applied Signal Processing Conference (ASPCON) · doi:10.1109/aspcon.2018.8748419
Near Optimal Disassembly Sequence Generation for Large Equipment in Nuclear Plant
Enomoto, A., Seki, H., Yoshida, T., TAHATA, J., Imamura, M., & NAGASE, H. (2019) · Genshiryoku bakkuendo kenkyu/Hōshasei haikibutsu kenkyū/Genshiryoku bakku endo kenkyū/Genshiryoku bakkuendo kenkyuu · doi:10.3327/jnuce.26.2_111
Biyela, P. (2017) · ResearchSpace (University of KwaZulu-Natal)
Chien, S.-T., Lin, F., Tsai, C., & Hsieh, H.-P. (2020) · IEEE International Conference on Mobile Data Management (MDM) · doi:10.1109/mdm48529.2020.00069
An Algorithm to Design a Scalable Control Layer for a Software-Defined Network
Kumar, S., Sethi, D. S., Kispotta, K., & Verma, D. (2021) · Lecture notes on data engineering and communications technologies · doi:10.1007/978-981-15-8335-3_57
Metodos de incremento e busca em grafos
Ribeiro, C. D. O. (1988) · Digital Library of Theses and Dissertations (Universidade de São Paulo) · doi:10.11606/d.45.1988.tde-20210729-000335
Realistic Human Mobility Model for Opportunistic Networks
Greede, A. (2022) · ICST Transactions on Mobile Communications and Applications · doi:10.4108/eai.2-5-2022.173976
Efficient Backhaul Design for 5G Ultra Dense Cells
Raithatha, M. (2020) · Carleton University's Institutional Repository (MacOdrum Library, Carleton University) · doi:10.22215/etd/2020-14228
Spatial Queries for Indoor Location-based Services
Liu, T. (2022) · VBN Forskningsportal (Aalborg Universitet) · doi:10.54337/aau470863740
NAJKRÓTSZA ŚCIEŻKA I CYKL EULERA – APLIKACJA ORAZ HISTORIA
Grygiel, M. (2022) · Akademia Techniczno-Humanistyczna w Bielsku-Białej eBooks · doi:10.53052/9788367652001.02
The Optimized path for the public transportation of Incheon in South KoreaPreprint
Faradonbe, S. M., Li, H., Kang, M., & Iim, C. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2309.10006
Research on Improved A* Path Planning Algorithm Based on Local Environment
Zhao, W., Zhu, W., & Ma, X. (2023) · China Automation Congress (CAC) · doi:10.1109/cac59555.2023.10451775
Motion Planning for Robotic Manipulation
Petrovic, I. K., Marić, F., Petrović, L., & Marković, I. (2024) · Rad Hrvatske akademije znanosti i umjetnosti Tehničke znanosti · doi:10.21857/m8vqrt3p19
Yau, S. S. ‐., Chen, X., Jiao, X., Kang, J., Sun, Z., & Tao, Y. (2024) · Algorithms and computation in mathematics · doi:10.1007/978-3-031-77684-7_4
Xing, R., Yang, Z., Zhang, X., Liang, Y., Yang, T., & Wang, F. (2025) · Journal of Advanced Transportation · doi:10.1155/atr/3589423
DEFENDCLI: {Command-Line} Driven Attack Provenance ExaminationPreprint
Wu, P., Sun, N., Moustafa, N., Qu, Y., & Ding, M. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2508.12553
Kumar, P., Pal, K., Kumar, P., Govil, M. C., Rajpoot, D. S., & Vidyarthi, A. (2025) · Transactions on Emerging Telecommunications Technologies · doi:10.1002/ett.70319
Design of highly distributed biofuel production systems
Luo, D. (2011) · SMARTech Repository (Georgia Institute of Technology)
Nonparametric Regression and Density Estimation on a Network
Liu, Y. (2020) · eCommons (Cornell University) · doi:10.7298/1epr-s184
Xuan, Q., & Li, C. (2021) · Institutional Repositories DataBase (IRDB) · doi:10.18910/84889
Implementation of Cache Attack on Real Information Centric Networking System
Anto Morais, F. J. (2018) · University of North Florida Digital Commons (University of North Florida)
Branch and Bound pattern in FastFlow
CECCHI, G. (2014) · Electronic Theses and Dissertations Repository (University of Pisa)
Trafikruttplanering med hjälp av grafiska neurala nätverk
Olsson, L. (2023) · DiVA (Linkoping University)
Elgaroui, L. (2021) · PolyPublie (École Polytechnique de Montréal)
Graph algorithms for approximate and dynamic settings in the external-memory model
Veith, D. (2020) · Publication Server of Goethe University Frankfurt am Main (Goethe University Frankfurt)
Wizdee Discovery - Colaboração e Personalização
Mateus, T. J. P. D. S. (2015) · Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT)
DISTRIBUTED ESTIMATION OF CENTRALITY MEASURES IN COMPLEX NETWORKS
Wang, W. (2016) · SHAREOK (University of Oklahoma; Oklahoma State University; Central Oklahoma University)
Practical and Efficient Stabilizability and Returning to Safety
Gong, Z. (2025) · eScholarship (California Digital Library)
YU, J., Zhang, X., Huang, D.-F., & Huang, X. Q. (2025) · SSRN Electronic Journal · doi:10.2139/ssrn.5682692
A aplicação de redes ao ramo da saúde
Amado, M. M. P. (2015) · Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT)
Unmanned Aerial Vehicle Path Optimization Using Particle Swarm Optimization with Obstacle Detection
Harin, N., Selvabharathi, S., Vivekan, S., Hemashree, P., Mahalakshmi, S. B., & Karthika, S. (2026) · Lecture notes in networks and systems · doi:10.1007/978-981-96-9682-6_16
Gusti, K. A., Arzufa, I. R., & Hamdani, C. N. (2025) · Prosiding Seminar Nasional Teknologi Energi dan Mineral · doi:10.53026/prosidingsntem.v5i1.619
SDrecall: a sensitive approach for variant detection in segmental duplications
Yang, X. T., She, C. H., Zhang, C., Leung, D., Yang, J., Chan, K. W., Duque, J. S. R., Lau, Y., & Yang, W. (2026) · Genome biology · doi:10.1186/s13059-025-03928-5
Parviziomran, I., Mahmoudi, M., Boloori, A., & Coelho, L. C. (2026) · Transportation Research Interdisciplinary Perspectives · doi:10.1016/j.trip.2026.101925
Analysis and modelling of spatial organization of 3D tissues in biological images
nhu, H. T. T. (2018) · theses.fr (ABES) · doi:10.70675/133a6a87z190fz4092z91d4z09136e03378a
The virtual network functions placement and routing problem
Mouaci, A. (2020) · theses.fr (ABES) · doi:10.70675/5fc2ffa2zb6e5z484fz9debz634357612240
Wang, Y., Gao, J., Song, W., Zhou, Z., Zhao, H., Li, J., & Xu, Y. (2026) · Intelligent Service Robotics · doi:10.1007/s11370-026-00695-5
Low-blocking topology control for dynamic LEO satellite optical communication networks
Higashimori, K., & Inoue, T. (2026) · Journal of Optical Communications and Networking · doi:10.1364/jocn.590655
Graph Analysis Algorithms on GPU
Zheng, Z. (2026) · Springer eBooks · doi:10.1007/978-981-95-5747-9_3
Lu, Y., Fan, J., Lin, X., Lan, S., Li, M., & Chiong, R. (2026) · Computers & Operations Research · doi:10.1016/j.cor.2026.107595
Tian, W. D., Shi, J. Y., & Yiu, M. L. (2026) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3770855.3818012
Azmi, R., Chenal, J., KHARBACH, O., Diop, E. B., Abdem, S. A. E., Lahlouh, A., Bounabi, M., & Chafiq, T. (2026) · Research Square · doi:10.21203/rs.3.rs-10668610/v1
Liu, Y., Liu, J., Zhang, R., Qiao, R., Tang, Q., & Huang, T. (2026) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2026.3727425
Inoue(Fujii), R. (2021) · Institutional Repositories DataBase (IRDB) · doi:10.15083/0002008637
Shang, S., Liu, Y., Yintang, W. A. N. G., Liu, G., Hu, J., Zhang, J., & Chen, X. (2026) · Sustainability · doi:10.3390/su182111186
Opportunistic Vehicular Assisted Ferrying in Energy Efficient Wireless Mesh Networks
Moghadam, K. R. (2011) · MacSphere (McMaster University) · doi:10.71548/13158
Even, G. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9781139015165.011
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
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.