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 201–300 of 380
A decomposition algorithm for locating a shortest path between two nodes in a network
Jarvis, J. J., & Tüfekçi, S. (1982) · Networks · doi:10.1002/net.3230120207 · Cited by 5
Swarm Herding: A Leader-Follower Framework For Multi-Robot NavigationPreprint
Xu, X., & Diaz-Mercado, Y. J. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.07416 · Cited by 5
FishFuzz: Throwing Larger Nets to Catch Deeper BugsPreprint
Zheng, H., Zhang, J., Huang, Y., Ren, Z., Wang, H., Cao, C., Zhang, Y., Toffalini, F., & Payer, M. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2207.13393 · Cited by 5
AutoDrone: Shortest Optimized Obstacle-Free Path Planning for Autonomous Drones
Jana, P. K., & Jana, D. (2022) · Algorithms for intelligent systems · doi:10.1007/978-981-19-1657-1_1 · Cited by 4
Simulation of AGV Airport Path Planning Based on Improved Breadth-First Search Algorithm
Shiwei, Z., Yangyang, Z., & Fei-long, H. (2024) · IEEE International Conference on Sensors, Electronics and Computer Engineering (ICSECE) · doi:10.1109/icsece61636.2024.10729370 · Cited by 4
Managing Congestion in Advanced Air Mobility Operations Using a Bi-Level Optimization Approach
Wu, H., Li, M. Z., Henderson, J. M., Bongo, E. M., & Weitz, L. A. (2025) · AIAA SciTech Forum · doi:10.2514/6.2025-0582 · Cited by 4
End-to-End Routing Algorithm Based on Max-Flow Min-Cut in SDN Controllers
Alzaben, N., & Engels, D. W. (2022) · International Conference on Advanced Communication Technology · doi:10.23919/icact53585.2022.9728780 · Cited by 4
Coverage Path Planning for Autonomous Road Sweepers in Obstacle-cluttered Environments
Yang, N., Zhang, W., & Yu, W. (2022) · IEEE Conference on Control Technology and Applications (CCTA) · doi:10.1109/ccta49430.2022.9966056 · Cited by 4
Gene Regulatory Networks from Gene Ontology
Liu, W., Chang, K., Zheng, J., Jain, D., Kim, J., & Rajapakse, J. C. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38036-5_12 · Cited by 4
Bahalkeh, E. (2015) · OhioLink ETD Center (Ohio Library and Information Network) · Cited by 4
Multiple feature‐based portal vein classification for liver segment extraction
Wu, C., Fu, T., Gao, Y., Liu, Y., Fan, J., Ai, D., Song, H., & Yang, J. (2021) · Medical Physics · doi:10.1002/mp.14745 · Cited by 4
Single-cell RNA sequencing data analysis based on non-uniformε−neighborhood network
Jia, J., & Chen, L. (2022) · Bioinformatics · doi:10.1093/bioinformatics/btac114 · Cited by 4
Applying Reinforcement Learning for Shortest Path Problem
Sun, Z. (2022) · International Conference on Big Data, Information and Computer Network (BDICN) · doi:10.1109/bdicn55575.2022.00100 · Cited by 4
Al-Ansarry, S., Al-Darraji, S., & Honi, D. G. (2023) · Iraqi Journal for Electrical And Electronic Engineering · doi:10.37917/ijeee.19.2.11 · Cited by 4
Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
Cantone, D. A., & Faro, S. (2013) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2013.03.005 · Cited by 4
Bakar, S. A., & Ibrahim, M. (2017) · AIP conference proceedings · doi:10.1063/1.4995893 · Cited by 4
Comparative Analysis and Route Optimization of State of the Art Routing Protocols
Khan, I. U., Qureshi, I. M., Shah, S. B. H., Akhlaq, M. H., Safi, A., Khan, M. A., & Nazir, E. A. (2018) · ICST Transactions on Mobile Communications and Applications · doi:10.4108/eai.22-3-2018.154385 · Cited by 3
Synthesis of Analog and Mixed-Signal Circuits on a Programmable Array
Chen, Z., & Savidis, I. (2025) · IEEE Transactions on Very Large Scale Integration (VLSI) Systems · doi:10.1109/tvlsi.2025.3553538 · Cited by 3
Tilewise Accumulated Cost Surface Computation with Graphics Processing Units
Kovanen, J., & Sarjakoski, T. (2015) · ACM Transactions on Spatial Algorithms and Systems · doi:10.1145/2803172 · Cited by 3
Ensemble Clustering via Adaptive Weight Adjustment and Cluster Generation in Difference Similarity
Wang, X., Liu, C., Zhang, H., & Wang, Y. (2023) · International Conference on Intelligent Systems and Knowledge Engineering (ISKE) · doi:10.1109/iske60036.2023.10481067 · Cited by 3
Routing problem for reducing significant outages in optical networks and its system analysis
Higashimori, K., Tanaka, T., & Inoue, T. (2024) · Journal of Optical Communications and Networking · doi:10.1364/jocn.520509 · Cited by 3
Norm Convergence in Populations of Dynamically Interacting Agents
Mungovan, D., Howley, E., & Duggan, J. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-17080-5_24 · Cited by 3
Empowering diabetes self-management by gamifying intelligent system: MyTrybeCare concept
Bouras, A., Usop, K., & Popescu, M. (2018) · Middle East Conference on Biomedical Engineering · doi:10.1109/mecbme.2018.8402421 · Cited by 3
A Cache Based DoS Attack on Real Information Centric Networking System
Morais, F. J. A., Roy, S., & Ahuja, S. P. (2018) · IEEE International Performance, Computing, and Communications Conference · doi:10.1109/pccc.2018.8710810 · Cited by 3
A new routing metric for real-time applications in smart cities
Elgaroui, L., Chamberland, S., & Pierre, S. (2019) · doi:10.1109/stict.2019.8789379 · Cited by 3
Development of Automatic Pipe Routing System Reflecting Design Knowledge
INOUE, R., OKUDA, K., & Ota, J. (2020) · Journal of the Japan Society for Precision Engineering · doi:10.2493/jjspe.86.502 · Cited by 3
Analysis of the Health Network of Metropolitan Lima Against Large-Scale Earthquakes
Núñez-del-Prado, M., & Barrera, J. (2021) · Communications in computer and information science · doi:10.1007/978-3-030-76228-5_32 · Cited by 3
End-to-End Routing Approach for SDN Based Wireless Ad Hoc Network
Alzaben, N., & Engels, D. W. (2021) · IEEE Symposium on Wireless Technology & Applications (ISWTA) · doi:10.1109/iswta52208.2021.9587405 · Cited by 3
MnM: A Fast and Efficient Min/Max Searching in MRAM
Sridharan, A., Zhang, F., & Fan, D. (2022) · ACM Great Lakes Symposium on VLSI (GLSVLSI) · doi:10.1145/3526241.3530349 · Cited by 3
PRM Based Motion Planning for Sequencing of Remote Laser Processing Tasks
Villumsen, S., & Kristiansen, M. (2017) · Procedia Manufacturing · doi:10.1016/j.promfg.2017.07.109 · Cited by 3
Ahmed, F., Anzum, F., Islam, M. N., Abdullah, W. M., Ahsan, S. A., & Rana, M. (2018) · IEEE/ACIS International Conference on Computer and Information Science (ICIS) · doi:10.1109/icis.2018.8466444 · Cited by 3
A Clustering Algorithm Based on Minimum Spanning Tree and Density
Chen, J., & Lu, J. X. (2019) · IEEE International Conference on Big Data Analytics (ICBDA) · doi:10.1109/icbda.2019.8713247 · Cited by 3
Influence maximization in graph-based OLAP (GOLAP)
Jin, J., Zhang, G., Sheu, P. C. ‐., Hayakawa, M., & Kitazawa, A. (2019) · Social Network Analysis and Mining · doi:10.1007/s13278-019-0598-2 · Cited by 3
A Structural Testing Model Using SDA Algorithm
Saju Sankar, S., & S, V. C. S. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-53956-6_36 · Cited by 3
Enabling Big Data Analytics and AI Solutions for Smart Warehouse
Er, N., Cidal, G. M., Ünsal, S., & CAKIR, A. M. (2021) · Lecture notes in networks and systems · doi:10.1007/978-3-030-85626-7_108 · Cited by 3
Comparison of Path Planning between Improved Informed and Uninformed Algorithms for Mobile Robot
Amr, M., Bahgat, A., Rashad, H., & Ibrahim, A. M. A. (2022) · International Journal of Advanced Computer Science and Applications · doi:10.14569/ijacsa.2022.0130629 · Cited by 3
Influence Maximization in GOLAP
Jin, J. (2019) · eScholarship (California Digital Library) · Cited by 3
A Distributed Shortest - Path Algorithm
Humblet, P. A. (1978) · Defense Technical Information Center (DTIC) · doi:10.21236/ada059838 · Cited by 3
Baklouti, Z. (2018) · theses.fr (ABES) · doi:10.70675/ac005290zc122z4a0dz9e6dz77b512269a2e · Cited by 3
Liang, X., Shangguan, W., & Zha, Y. (2024) · China Automation Congress (CAC) · doi:10.1109/cac63892.2024.10865377 · Cited by 2
Even, G. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9781139015165.004 · Cited by 2
Design and Implementation of Optimal Path Search Service Using GPS Information in Photo File
Kim, J.-Y., & Kim, S.-G. (2012) · Journal of the Korea Society of Computer and Information · doi:10.9708/jksci/2012.17.12.199 · Cited by 2
Akram, M., & Cho, T. H. (2017) · Symmetry · doi:10.3390/sym9100220 · Cited by 2
Yue, Y., Yan, X., Wang, S., Li, M., & Faghri, A. (2023) · Transportation Research Record Journal of the Transportation Research Board · doi:10.1177/03611981231182150 · Cited by 2
Physarum-Inspired Solutions to Network Optimization Problems
Zhang, X., & Yan, C. (2018) · Emergence, complexity and computation · doi:10.1007/978-3-319-77510-4_12 · Cited by 2
Railway Travel-Time Optimization System
Otuneme, N. (2018) · International Journal of Engineering Research and · doi:10.17577/ijertv7is110062 · Cited by 2
An Improved A* Algorithm Based on Divide-and-Conquer Method for Golf Unmanned Cart Path Planning
Yi, C., Xie, L., He, W., Jiang, Q. F., & Xu, J. (2019) · Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-030-22968-9_46 · Cited by 2
Improved Traffic Sign Detection In Videos Through Reasoning Effective RoI Proposals
Zhang, Y., Qi, Y., Yang, J., & Hwang, J. (2020) · IEEE International Conference on Multimedia and Expo (ICME) · doi:10.1109/icme46284.2020.9102896 · Cited by 2
Optimum Route Computation in a Chaotic Artificial Climbing Wall
Seal, D., & Seal, R. (2022) · Lecture notes in networks and systems · doi:10.1007/978-981-16-5987-4_68 · Cited by 2
Locality-aware virtual machine placement based on similarity properties in mobile edge computing
Amjad, D. M., & Eslamnour, B. (2024) · Cluster Computing · doi:10.1007/s10586-024-04346-1 · Cited by 2
Feng, W., Liu, K., Sun, S., Cheng, B. H., & Zhang, W. (2024) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2024.103920 · Cited by 2
Block Configuration Algorithms for a Reconfigurable Analog Array
Chen, Z., & Savidis, I. (2024) · IEEE International Symposium on Circuits and Systems proceedings · doi:10.1109/iscas58744.2024.10558121 · Cited by 2
A decision support tool for weather and terrain avoidance during departure
Cauchi, N., Theuma, K., Zammit, C., Gauci, J., & Zammit-Mangion, D. (2015) · IEEE/AIAA Digital Avionics Systems Conference (DASC) · doi:10.1109/dasc.2015.7311384 · Cited by 2
Application of Angle Related Cost Function Optimization for Dynamic Path Planning Algorithm
Zeng, M., Yang, X., Wang, M., & Xu, B. (2018) · Algorithms · doi:10.3390/a11080127 · Cited by 2
Path-planning in Discretized Environments with Optimized Waypoints Computation
Vitolo, E., Mahulea, C., & Kloetzer, M. (2018) · IEEE International Conference on Emerging Technologies and Factory Automation (ETFA) · doi:10.1109/etfa.2018.8502504 · Cited by 2
A Vertical Breadth-First Multilevel Path Algorithm to Find All Paths in a Graph
Singh, M., Anu, V. K., & Walia, G. (2019) · Studies in big data · doi:10.1007/978-3-030-32587-9_10 · Cited by 2
Construction of Psychological Crisis Assessment Model Based on Machine Learning
Li, H., Yang, Z., Wang, Y., Yao, L., & Zhao, X. (2019) · IEEE International Smart Cities Conference (ISC2) · doi:10.1109/isc246665.2019.9071687 · Cited by 2
An Experimental Analysis of Indoor Spatial Queries: Modeling, Indexing, and Processing
Liu, T., Li, H., Lu, H. C., Cheema, M. A., & Shou, L. (2020) · VBN Forskningsportal (Aalborg Universitet) · doi:10.48550/arxiv.2010.03910 · Cited by 2
Sankai, H., Saito, A., & Sankai, Y. (2020) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/smc42975.2020.9283153 · Cited by 2
Identifying Anomaly Work in Intralogistics Using BLE and LPWA
Yamaguchi, M., Yuasa, N., Yoshimura, Y., & Otsuka, T. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-79463-7_45 · Cited by 2
Ahn, J., & Cho, T. H. (2022) · IEEE Access · doi:10.1109/access.2022.3202541 · Cited by 2
Peng, T., Tang, D., & Wu, J. (2023) · Journal of Physics Conference Series · doi:10.1088/1742-6596/2419/1/012088 · Cited by 2
ALRP: An Adaptive Link State Routing Protocol for Multi-Identifier Network
Wang, F., Li, H., Wu, Z., Lü, P., Wang, B., Yang, Y., Bai, H., & Pei, X. (2022) · IEEE International Conference on Computer and Communications (ICCC) · doi:10.1109/iccc56324.2022.10066013 · Cited by 2
Investigating the min‐cost minimum fleet problem through taxi data analysis
Nie, W., Cai, S., Zhao, Z., Li, Z., Zhou, T., & Zhang, Y. (2023) · Computer-Aided Civil and Infrastructure Engineering · doi:10.1111/mice.13106 · Cited by 2
MSO-GP: 3-D segmentation of large and complex conjoined tree structures
De, A., Das, N., Saha, P. K., Comellas, A. P., Hoffman, E. A., Basu, S., & Chakraborti, T. (2024) · Methods · doi:10.1016/j.ymeth.2024.05.016 · Cited by 2
Jourquin, B., Koul, C., & Beuthe, M. (1999) · DIAL (Catholic University of Leuven) · doi:10.13140/2.1.2390.1444 · Cited by 2
Tüfekçi, S. (1983) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800300303 · Cited by 2
Network Update and Service Chain Management in Software Defined Networks
Chen, Y. (2020) · TUScholarShare (Temple University) · Cited by 2
Makni, I. (2022) · theses.fr (ABES) · doi:10.70675/a168761czc719z435bz92fazb8fe8f63c53d · Cited by 2
Abdelmoula, M. (2014) · theses.fr (ABES) · doi:10.70675/384aa4bbzc607z4077zb165z8c8dfd910f34 · Cited by 2
Traffic congestion reduction based on vehicle platoons and intelligent crossroads interactions
Du, W. (2021) · theses.fr (ABES) · doi:10.70675/54f6f755z1941z42c8zb92fze5dd1c5d8994 · Cited by 2
Review on Technology of Cooperative Flight for Low-Altitude Unmanned Aerial Swarms
Zhai, S., Han, J., Ma, Z., Nan, B., Zhang, L., & Zhang, K. (2024) · Lecture notes in electrical engineering · doi:10.1007/978-981-97-3340-8_37 · Cited by 1
Omwansu, W., Musembi, R. J., & Derese, S. (2024) · Physical Chemistry Chemical Physics · doi:10.1039/d4cp02123a · Cited by 1
On the k-maximally-disjoint weighted spanning trees problem: variants, complexity and algorithms
Astaoui, W., Magnouche, Y., & Martin, S. (2025) · Annals of Operations Research · doi:10.1007/s10479-025-06592-x · Cited by 1
Guo, J., Wang, C., & Wang, L. (2025) · Applied Sciences · doi:10.3390/app15105319 · Cited by 1
Exploring Dendritic Computation in Bio-Inspired Architectures for Dynamic Programming
Das, A. K. (2025) · Design, Automation, and Test in Europe · doi:10.23919/date64628.2025.10992728 · Cited by 1
Optimal transport in non-convex geometries and its application in shrinkage porosity prediction
Nouri, M., Kazemzadeh‐Parsi, M. J., Ammar, A., Chinesta, F., Artozoul, J., & Caillaud, A. (2025) · Computers & Mathematics with Applications · doi:10.1016/j.camwa.2025.06.012 · Cited by 1
A Fast and Simple Algorithm for the Resource Constrained Shortest Path Problem
Ahmadi, S., Raith, A., & Jalili, M. (2025) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.esa.2025.97 · Cited by 1
Wang, Y., Gao, J., Song, W., Zhou, Z., Zhao, H., Li, J., & Xu, Y. (2025) · Intelligent Service Robotics · doi:10.1007/s11370-025-00658-2 · Cited by 1
Yuan, Z., Ghias, A. M. Y. M., Cui, C., Lin, P., Pou, J., & Dong, Z. Y. (2026) · Applied Energy · doi:10.1016/j.apenergy.2026.127938 · Cited by 1
Adaptive Hierarchical Evaluation of LLMs and SAST tools for CWE Prediction in Python
Adnan, M., & Kuhn, C. C. N. (2026) · International Conference on Advances in Artificial Intelligence and Machine Learning (AAIML) · doi:10.1109/aaiml67890.2026.11498216 · Cited by 1
Path querying system on mobile devices
Lin, X., Wang, Y., Tian, Y., & Wu, L. (2005) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.673672 · Cited by 1
Eliminating Duplicated Paths to Reduce Computational Cost of Rule Generation by Using SDN
Sim, J.-H., Kim, S., Park, M.-W., & Chung, T. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-09153-2_45 · Cited by 1
A robust and reliable quantification method for Focal Arteriolar Narrowing in color retinal image
Roy, P. K., Hussain, A., Bhuiyan, A., Kawasaki, R., & Ramamohanarao, K. (2015) · IEEE International Symposium on Biomedical Imaging (ISBI) · doi:10.1109/isbi.2015.7164164 · Cited by 1
An Efficient Algorithm for 3D NoC Architecture Optimization
Jiang, X., Zhang, R., & Watanabe, T. (2013) · IPSJ Transactions on System and LSI Design Methodology · doi:10.2197/ipsjtsldm.6.34 · Cited by 1
Runtime Computation of Optimal Offloading Scheduling
Morichetta, A., Re, B., & Tiezzi, F. (2018) · IEEE International Conference on Mobile Cloud Computing, Services, and Engineering (MobileCloud) · doi:10.1109/mobilecloud.2018.00019 · Cited by 1
Khan, I. U., Qureshi, I. M., Khan, M. A., Shah, S. B. H., Ansari, I. S., & Akhlaq, M. H. (2018) · International Conference on Future Networks and Distributed Systems (ICFNDS) · doi:10.1145/3231053.3231117 · Cited by 1
Optimization of Black-Start Scheme for Mitigating Overvoltage
Zhang, L., Jing, Z., Ji, T., & Sun, Y. (2019) · IEEE Innovative Smart Grid Technologies-Asia · doi:10.1109/isgt-asia.2019.8880800 · Cited by 1
UCarpooling: decongesting traffic through carpoolingusing automatic pairings
González, M., Lugo, A., Aquino, N., Cernuzzi, L., & Chenú-Abente, R. (2021) · CLEI electronic journal · doi:10.19153/cleiej.24.2.10 · Cited by 1
A Comparative Study on Shortest Path Visualization using Artificial Intelligence
Patel, G. M., Singh, A. P., Bhala, T., Jora, A., & Chandna, D. (2021) · International Conference on Reliability, Infocom Technologies and Optimization (Trends and Future Directions) (ICRITO) · doi:10.1109/icrito51393.2021.9596550 · Cited by 1
End-to-End Routing in SDN Controllers Using Max-Flow Min-Cut Route Selection Algorithm
Alzaben, N., & Engels, D. W. (2022) · International Conference on Advanced Communication Technology · doi:10.23919/icact53585.2022.9728920 · Cited by 1
The Free Path Planner Based on Windmill Decomposition
Jan, G. E., Luo, C., Lee, M.-C., & Hsieh, H.-C. (2022) · International Conference on Artificial Intelligence, Robotics and Control (AIRC) · doi:10.1109/airc56195.2022.9836984 · Cited by 1
Travel purpose identification based on mobile phone signaling data and Bayesian network
Lu, Z., Chai, L., Feng, Z., & Liu, J. (2022) · International Conference on Frontiers of Traffic and Transportation Engineering (FTTE) · doi:10.1117/12.2652397 · Cited by 1
A Monte Carlo tree search-based method for decision making of generator serial restoration sequence
Xu, W., Chen, S., Han, G., Yu, N., & Xu, H. (2023) · Frontiers in Energy Research · doi:10.3389/fenrg.2022.1007914 · Cited by 1
Research on Path Planning Approach of Mobile Robot based on A*-SPF in Complex Environment
Wu, J., Yu, J., Zhao, Z., Chen, Z., Xu, J., Yang, L., & Chen, Y. (2023) · Youth Academic Annual Conference of Chinese Association of Automation (YAC) · doi:10.1109/yac59482.2023.10401579 · Cited by 1
Efficient Routing Method for Reducing Significant Outages in Optical Networks
Higashimori, K., Tanaka, T., & Inoue, T. (2023) · Globecom · doi:10.1109/globecom54140.2023.10437754 · Cited by 1
Path Planning Algorithm for Mobile Robots
Jian, H. (2024) · Transactions on Computer Science and Intelligent Systems Research · doi:10.62051/ajnbr762 · Cited by 1
G-FARS: Gradient-Field-Based Auto-Regressive Sampling for 3D Part Grouping
Cheng, J., & Stathaki, T. (2024) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr52733.2024.02611 · Cited by 1
Sistema de computación ubicua para relacionar a personas con discapacidad visual con su entorno
Jiménez, E., & Adrián, R. (2015) · Universidad de Chile · Cited by 1
Agent Modeling In Decision Support System: A Case Study In A Base Hospital System
Nakhwal, A. (2011) · Scholarship at UWindsor (University of Windsor) · Cited by 1
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.