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 101–200 of 380
Unsupervised discriminative feature representation via adversarial auto-encoder
Guo, W., Cai, J., & Wang, S. (2019) · Applied Intelligence · doi:10.1007/s10489-019-01581-7 · Cited by 19
Xu, M., Huang, W., Xu, M., Lei, J., & Chen, H. (2022) · Molecules · doi:10.3390/molecules28010321 · Cited by 18
Scheduling large-scale scientific workflow on virtual machines with different numbers of vCPUs
Wu, H., Chen, X., Song, X., Zhang, C., & Guo, H. (2020) · The Journal of Supercomputing · doi:10.1007/s11227-020-03273-3 · Cited by 18
Dong, D., Lam, W., & Sun, D. B. (2020) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2020.3013846 · Cited by 18
Kong, P., Wang, J.-C., Tseng, K.-S., Yang, Y.-C., Wang, Y., & Jiang, J. (2020) · International Journal of Electrical Power & Energy Systems · doi:10.1016/j.ijepes.2020.106394 · Cited by 17
Analysis of the implicit trust within the OLSR protocol
Adnane, A., de Sousa, R. T., Bidan, C., & Mé, L. (2007) · IFIP International Federation for Information Processing/IFIP · doi:10.1007/978-0-387-73655-6_6 · Cited by 17
Parallel algorithms for the single source shortest path problem
Mateti, P., & Deo, N. (1982) · Computing · doi:10.1007/bf02254849 · Cited by 17
DutyTTE: Deciphering Uncertainty in Origin-Destination Travel Time Estimation
Mao, X., Lin, Y., Guo, S., Chen, Y., Xian, X., Wen, H., Xu, Q., Lin, Y., & Wan, H. (2025) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v39i12.33350 · Cited by 16
A Novel Forwarding and Caching Scheme for Information-Centric Software-Defined Networks
Raza, K. A., Asheralieva, A., Karim, M. M., Sharif, K., Gheisari, M., & Khan, S. (2021) · International Symposium on Networks, Computers and Communications (ISNCC) · doi:10.1109/isncc52172.2021.9615667 · Cited by 16
Rahman, M. M. H., Al-Naeem, M., Banerjee, A., & Sufian, A. (2023) · Applied Sciences · doi:10.3390/app13042535 · Cited by 16
SmallMap: Low-cost Community Road Map Sensing with Uncertain Delivery Behavior
Hong, Z., Wang, H., Ding, Y. C., Wang, G., He, T., & Zhang, D. (2024) · Proceedings of the ACM on Interactive Mobile Wearable and Ubiquitous Technologies · doi:10.1145/3659596 · Cited by 16
Monestiez, P., & Kretzschmar, A. (1992) · Soil Biology and Biochemistry · doi:10.1016/0038-0717(92)90149-r · Cited by 16
Liu, W., & Rajapakse, J. C. (2019) · BMC Systems Biology · doi:10.1186/s12918-019-0695-x · Cited by 15
Multihop Routing Enabled Packet Switching With QoS Guarantee in Optical Clos for Data Centers
Zhao, Z., Wu, B., Li, B., Xiao, J., Fu, S., & Liu, D. (2018) · Journal of Optical Communications and Networking · doi:10.1364/jocn.10.000624 · Cited by 15
A Fast Heuristic for Gateway Location in Wireless Backhaul of 5G Ultra-Dense Networks
Raithatha, M., Chaudhry, A. U., Hafez, R. H. M., & Chinneck, J. W. (2021) · IEEE Access · doi:10.1109/access.2021.3062655 · Cited by 15
ARCTURUS : Full Coverage Binary Similarity Analysis with Reachability-guided Emulation
Zhou, A., Hu, Y., Xu, X., & Zhang, C. (2024) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/3640337 · Cited by 14
Wei, Z., & Mukherjee, S. (2024) · Risk Analysis · doi:10.1111/risa.16873 · Cited by 14
Max-PIM: Fast and Efficient Max/Min Searching in DRAM
Zhang, F., Angizi, S., & Fan, D. (2021) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1109/dac18074.2021.9586096 · Cited by 14
Cache attacks on blockchain based information centric networks: an experimental evaluation
Roy, S., Morais, F. J. A., Salimitari, M., & Chatterjee, M. (2019) · International Conference on Distributed Computing and Networking (ICDCN) · doi:10.1145/3288599.3288640 · Cited by 14
Identifying OSPF LSA falsification attacks through non-linear analysis
Al-Musawi, B. Q., Branch, P., Hassan, M. F., & Pokhrel, S. R. (2019) · Computer Networks · doi:10.1016/j.comnet.2019.107031 · Cited by 14
An optimum vehicular path algorithm for traffic network based on hierarchical spatial reasoning
Lu, F., Chenghu, Z., & Qing, W. (2000) · Geo-spatial Information Science · doi:10.1007/bf02829394 · Cited by 14
Online Games Traffic Multiplexing: Analysisand Effect in Access Networks
Saldaña, J. (2012) · KSII Transactions on Internet and Information Systems · doi:10.3837/tiis.2012.10.010 · Cited by 13
Liu, J., Kang, X., Dong, C., & Zhang, F. (2018) · Intelligent Automation & Soft Computing · doi:10.31209/2018.100000013 · Cited by 13
The Virtue of Patience: Offloading Topical Cellular Content through Opportunistic Links
Peng, W., Li, F., Zou, X., & Wu, J. (2013) · IEEE International Conference on Mobile Ad-Hoc and Sensor Systems (MASS) · doi:10.1109/mass.2013.69 · Cited by 13
Ammal, R. A., Sajimon, P. C., & S, V. C. S. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-61833-3_53 · Cited by 13
Zhang, K., Chen, Y., Cui, C., Wu, P., Miao, L., & Chen, B. (2022) · IET Intelligent Transport Systems · doi:10.1049/itr2.12215 · Cited by 12
Exact Multi-objective Path Finding with Negative Weights
Ahmadi, S., Sturtevant, N., Harabor, D., & Jalili, M. (2024) · Proceedings of the International Conference on Automated Planning and Scheduling · doi:10.1609/icaps.v34i1.31455 · Cited by 12
FraudMove: Fraud Drivers Discovery Using Real-Time Trajectory Outlier Detection
Eldawy, E. O., Hendawi, A., Abdalla, M., & Mokhtar, H. M. O. (2021) · ISPRS International Journal of Geo-Information · doi:10.3390/ijgi10110767 · Cited by 12
Kim, J. W., & Kim, S. K. (2016) · The Journal of Supercomputing · doi:10.1007/s11227-016-1687-x · Cited by 12
Chang, I.-C., Tai, H.-T., Hsieh, D.-L., Yeh, F.-H., & Chang, S. B. (2013) · International Symposium on Biometrics and Security Technologies · doi:10.1109/isbast.2013.17 · Cited by 11
An interactive approach for deriving geometric network models in 3D indoor environments
Luo, F., Cao, G., & Li, X. (2014) · doi:10.1145/2676528.2676531 · Cited by 11
Qin, K., Wang, Y., & Wang, B. (2018) · Information · doi:10.3390/info9100258 · Cited by 11
User interest-based recommender system for image-sharing social media
Kim, K., Kim, J., Kim, M. H., & Sohn, M. M. (2020) · World Wide Web · doi:10.1007/s11280-020-00832-9 · Cited by 11
End-to-End Routing in SDN Controllers Using Max-Flow Min-Cut Route Selection Algorithm
Alzaben, N., & Engels, D. W. (2021) · International Conference on Advanced Communication Technology · doi:10.23919/icact51234.2021.9371006 · Cited by 11
REASAN: Learning Reactive Safe Navigation for Legged RobotsPreprint
Yuan, Q., Cao, Z., Cao, M., & Li, K. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2512.09537 · Cited by 11
Li, W., Li, Z.-Y., & Luo, Q. (2023) · IET Intelligent Transport Systems · doi:10.1049/itr2.12476 · Cited by 10
Reliable Routing Strategies on Urban Transportation Networks
Yamín, D., Medaglia, A. L., & Prakash, A. (2024) · Transportation Science · doi:10.1287/trsc.2023.0013 · Cited by 10
UniTE: A Survey and Unified Pipeline for Pre-Training Spatiotemporal Trajectory Embeddings
Lin, Y. D., Zhou, Z., Liu, Y., Lv, H., Wen, H., Li, T., Li, Y., Jensen, C. S., Guo, S., Lin, Y., et al. (2024) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2024.3523996 · Cited by 10
Cellular Automata Applications in Shortest Path Problem
Tsompanas, M., Dourvas, N. I., Ioannidis, K., Sirakoulis, G. C., Hoffmann, R., & Adamatzky, A. (2018) · Emergence, complexity and computation · doi:10.1007/978-3-319-77510-4_8 · Cited by 10
Identifying the leaders and main conspirators of the attacks in terrorist networks
Rai, A. K., & Kumar, S. (2022) · ETRI Journal · doi:10.4218/etrij.2021-0239 · Cited by 10
A Multi-Stage Metaheuristic Algorithm for Shortest Simple Path Problem With Must-Pass Nodes
Su, Z., Zhang, J., & Lu, Z. (2019) · IEEE Access · doi:10.1109/access.2019.2908011 · Cited by 10
Adaptive routing of multiple taxis by mutual exchange of pathways
Yamamoto, K., Uesugi, K., & Watanabe, T. (2009) · International Journal of Knowledge Engineering and Soft Data Paradigms · doi:10.1504/ijkesdp.2010.030466 · Cited by 10
Explaining the Power of Topological Data Analysis in Graph Machine LearningPreprint
Taiwo, F. M., Islambekov, U., & Akçora, C. G. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2401.04250 · Cited by 10
Liu, J., Zhang, Y., Bian, S., Song, R., Zhang, C., Wei, Y.-Q., & Hua, C. (2025) · IEEE Transactions on Industrial Electronics · doi:10.1109/tie.2025.3574520 · Cited by 9
Mobile Application based Indoor Positioning and Navigational System using Dijkstra’s Algorithm
Nayagam, R. D., Selvathi, D., Geeta, R., Gopinath, D., & Sivakumar, G. (2023) · Journal of Physics Conference Series · doi:10.1088/1742-6596/2466/1/012007 · Cited by 9
Galliot: Path Merging Based Betweenness Centrality Algorithm on GPU
Zheng, Z., Zhao, C. X., Xie, P., & Du, B. (2023) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom53939.2023.10229018 · Cited by 9
Spatial-Temporal Bipartite Graph Attention Network for Traffic Forecasting
Lakmal, D., Perera, K., Borovica‐Gajic, R., & Karunasekera, S. A. (2024) · Lecture notes in computer science · doi:10.1007/978-981-97-2253-2_6 · Cited by 9
Etaqa-MG1: an efficient technique for the analysis of a class of M/G/1-type processes by aggregation
Ciardo, G., Mao, W., Riska, A., & Smirni, E. (2004) · Performance Evaluation · doi:10.1016/j.peva.2003.11.001 · Cited by 9
Zhen, Q., Zhang, A., Bokel, R., Zheng, Y., Li, J., Du, Y., & Zhang, Q. (2024) · Journal of Building Engineering · doi:10.1016/j.jobe.2024.109328 · Cited by 9
Kang, Y.-S., & Youm, S. (2016) · Multimedia Tools and Applications · doi:10.1007/s11042-016-4015-9 · Cited by 9
Chambers, S. N., McMahan, B., & Bongers, C. C. W. G. (2020) · Spatial and Spatio-temporal Epidemiology · doi:10.1016/j.sste.2020.100363 · Cited by 9
Quantum Algorithms for Trust-Based AI Applications
Kaur, D., Uslu, S., & Durresi, A. (2023) · Lecture notes on data engineering and communications technologies · doi:10.1007/978-3-031-35734-3_1 · Cited by 9
Indoor Taxi-Cab: Real-Time Indoor Positioning and Location-Based Services with Ekahau and Android OS
Kilinc, C., Mostafa, S. A. M., Islam, R. U., Shahzad, K., & Andersson, K. (2014) · International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS) · doi:10.1109/imis.2014.99 · Cited by 9
MAMRL: Exploiting Multi-agent Meta Reinforcement Learning in WAN Traffic EngineeringPreprint
Sun, S., Kiran, M., & Ren, W. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.15087 · Cited by 9
Qazzaz, M. M. H., Salama, A., Hafeez, M., & Zaidi, S. A. R. (2025) · IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS) · doi:10.1109/infocomwkshps65812.2025.11152963 · Cited by 8
Detection-by-tracking of traffic signs in videos
Zhang, Y., Wang, Z., Song, R., Yan, C., & Qi, Y. (2021) · Applied Intelligence · doi:10.1007/s10489-021-02838-w · Cited by 8
Process Knowledge Integrated Assembly Sequence Planning for Control Panel
Enomoto, A., Yamamoto, N., Yamamura, Y., & Sugawara, Y. (2020) · International Journal of Automation Technology · doi:10.20965/ijat.2020.p0006 · Cited by 8
Optimal GPS Integrity-Constrained Path Planning for Ground Vehicles
Maaref, M., & Kassas, Z. M. (2020) · IEEE/ION Position Location and Navigation Symposium · doi:10.1109/plans46316.2020.9109898 · Cited by 8
Compute Optimal Travel Duration in Eco-Driving applications
Ciarla, V., Chasse, A., Moulin, P., & Ojeda, L. L. (2016) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2016.08.076 · Cited by 8
Adoption of innovative eHealth services in prehospital emergency management: a case study
Tsiknakis, M., & Spanakis, M. (2010) · IEEE International Conference on Information Technology and Applications in Biomedicine · doi:10.1109/itab.2010.5687752 · Cited by 8
Solving the Shortest Path Problem with QAOA
Fan, Z., Xu, J., Shu, G., Ding, X., Lian, H., & Shan, Z. (2022) · SPIN · doi:10.1142/s2010324723500029 · Cited by 7
Integrating Railroad Crossing Blockage Information in First Responder Dispatching Route Planning
Wu, X., Chen, Y., & Qian, Y. (2024) · Journal of Transportation Engineering Part A Systems · doi:10.1061/jtepbs.teeng-7925 · Cited by 7
UVTM: Universal Vehicle Trajectory Modeling With ST Feature Domain Generation
Lin, Y. D., Hu, J., Guo, S., Yang, B., Jensen, C. S., Lin, Y., & Wan, H. (2025) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2025.3570428 · Cited by 7
Fault-Tolerant Application-Specific Topology-Based NoC and Its Prototype on an FPGA
Bhanu, P. V., Govindan, R., Kumar, R., Singh, V., Soumya, J., & Cenkeramaddi, L. R. (2021) · IEEE Access · doi:10.1109/access.2021.3082852 · Cited by 7
de Sousa, R. T., Adnane, A., Bidan, C., & Mé, L. (2009) · IEEE Latin America Transactions · doi:10.1109/tla.2009.5361198 · Cited by 7
Energy-optimal Path Planning with Active Flow Perception for Autonomous Underwater Vehicles
Yang, N., Chang, D., Johnson‐Roberson, M., & Sun, J. (2021) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra48506.2021.9561865 · Cited by 7
A general framework for shortest path algorithms
Pijls, W., & Kolen, A. W. J. (1992) · RePub (Erasmus University Rotterdam) · Cited by 7
Indoor Spatial Queries: Modeling, Indexing, and Processing
Liu, T., Li, H., Lu, H. C., Cheema, M. A., & Shou, L. (2021) · Monash University Research Portal (Monash University) · doi:10.5441/002/edbt.2021.17 · Cited by 6
Bulut, V., Onan, A., & Şenyayla, B. (2024) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2024.108821 · Cited by 6
Nam, S. M., & Cho, T. H. (2020) · International Journal of Distributed Sensor Networks · doi:10.1177/1550147720949134 · Cited by 6
A novel similarity measure for mining missing links in long-path networks
Ran, Y., Liu, T., Jia, T., & Xu, X.-K. (2021) · Chinese Physics B · doi:10.1088/1674-1056/ac4483 · Cited by 6
Urban high‐quality navigation path planning that integrates human emotion perception learning
Liu, S., Long, Y., Zhang, L., & Huang, Y. (2023) · Transactions in GIS · doi:10.1111/tgis.13119 · Cited by 6
A metric for dynamic routing based on variational principles
Sukhov, A. M., & Chemodanov, D. (2013) · Journal of High Speed Networks · doi:10.3233/jhs-130470 · Cited by 6
An Efficient Admission Control Algorithm for Virtual Sensor Networks
Ajmal, S. M., Paris, S., Zhang, Z., & Naït‐Abdesselam, F. (2014) · IEEE International Conference on High Performance Computing and Communications; IEEE International Conference on Smart City; IEEE International Conference on Data Science and Systems (HPCC/SmartCity/DSS) · doi:10.1109/hpcc.2014.113 · Cited by 6
A survey on network path identification using bio inspired algorithms
Arun, K., & Rejimoan, R. (2016) · International Conference on Advances in Electrical, Electronics, Information, Communication and Bio-Informatics · doi:10.1109/aeeicb.2016.7538314 · Cited by 6
Yang, T., Wolff, F., & Papachristou, C. (2018) · IEEE National Aerospace and Electronics Conference (NAECON) · doi:10.1109/naecon.2018.8556715 · Cited by 6
Data Aggregation Aware Routing for Distributed Training
Chen, Z., Long, X., Wu, Y., Chen, L., Wu, J., & Liu, S. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-69244-5_21 · Cited by 6
Grötschel, M. (2012) · Documenta mathematica series · doi:10.4171/dms/6 · Cited by 6
Constraint checking for restriction site mapping
Ho, S. T. S., Allison, L., Yee, C. N., & Dix, T. I. (2002) · Hawaii International Conference on System Sciences (HICSS) · doi:10.1109/hicss.1991.183933 · Cited by 6
A long term goal recommender approach for learning environments
Rafsanjani, N. (2018) · Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT) · doi:10.34626/5sjg-hz19 · Cited by 6
DESTA: A Framework for Safe Reinforcement Learning with Markov Games of InterventionPreprint
Mguni, D., Islam, U., Sun, Y., Zhang, X., Jennings, J., Sootla, A., Yu, C., Wang, Z., Wang, Y.-X., & Yang, Y. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.14468 · Cited by 6
Trustworthy AI: Ensuring Explainability & Acceptance
Kaur, D. (2023) · IUScholarWorks (Indiana University) · doi:10.7912/e4et-j067 · Cited by 6
Resource Constrained Pathfinding with Enhanced Bidirectional A* Search
Ahmadi, S., Raith, A., Tack, G., & Jalili, M. (2025) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v39i25.34892 · Cited by 5
Perancangan Jalur Evakuasi Kebakaran PT. PCC dengan Metode Algoritma Dijkstra
Azis, R., Nugrahadi, B., Devi, A. O. T., & Primasanti, Y. (2024) · JURNAL TEKNIK MESIN INDUSTRI ELEKTRO DAN INFORMATIKA · doi:10.55606/jtmei.v3i3.4208 · Cited by 5
Dynamic Topology Control of LEO Satellite Networks for Non-uniformly Distributed Traffic
Higashimori, K., & Inoue, T. (2024) · Globecom · doi:10.1109/globecom52923.2024.10901258 · Cited by 5
A Survey of Cell Decomposition-based Path Planning
Jan, G. E., Luo, C., Yang, C., & Hsieh, H.-C. (2023) · International Conference on Artificial Intelligence, Robotics and Control (AIRC) · doi:10.1109/airc57904.2023.10303086 · Cited by 5
Triyono, L., Gernowo, R., Prayitno, P., Cholil, S. R., Hestiningsih, I., Wiktasari, & Fahriah, S. (2023) · E3S Web of Conferences · doi:10.1051/e3sconf/202344802042 · Cited by 5
Querying Numeric-Constrained Shortest Distances on Road Networks
Yang, M., Li, W., Wang, W., Wen, D., & Qin, L. (2024) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde60146.2024.00194 · Cited by 5
The Shortest Path Parallel Algorithm on Single Source Weighted Multi-level Graph
Peng, Q., Yu, Y., & Wei, W. (2009) · doi:10.1109/wcse.2009.819 · Cited by 5
Power-aware server selection in nano data center
Sheikh, F., Fazal, H., Taqvi, F., & Shamsi, J. A. (2015) · IEEE Conference on Local Computer Networks Workshops (LCN Workshops) · doi:10.1109/lcnw.2015.7365927 · Cited by 5
Roy, P. K., Bhuiyan, A., Lee, K., Wong, T. Y., & Ramamohanarao, K. (2016) · Computers in Biology and Medicine · doi:10.1016/j.compbiomed.2016.04.018 · Cited by 5
TGE: Machine Learning Based Task Graph Embedding for Large-Scale Topology Mapping
Choi, J. Y., Logan, J. S., Wolf, M., George Ostrouchov, A., Kurç, T., Liu, Q., Podhorszki, N., Klasky, S., Romanus, M., Sun, Q., et al. (2017) · IEEE International Conference on Cluster Computing (CLUSTER) · doi:10.1109/cluster.2017.67 · Cited by 5
The advantage of the arduino sensing system on parking guidance information systems
Huang, K. Y., Chang, S. B., & Tsai, P. R. (2017) · IEEE International Conference on Industrial Engineering and Engineering Management (IEEM) · doi:10.1109/ieem.2017.8290258 · Cited by 5
An algorithm for the determination of longest distances in a graph
Noltemeier, H. (1975) · Mathematical Programming · doi:10.1007/bf01681355 · Cited by 5
Improving Context Awareness Information Retrieval with Online Social Networks
Lee, H., & Kwon, J. (2011) · ACIS/JNU International Conference on Computers, Networks, Systems and Industrial Engineering · doi:10.1109/cnsi.2011.54 · Cited by 5
Research on Crowdsourcing Emergency Information Extraction of Based on Events' Frame
Yang, B., Wang, J., Ma, W., & Mao, X. (2018) · Journal of Physics Conference Series · doi:10.1088/1742-6596/933/1/012009 · Cited by 5
Zhang, W., Zhang, L., & Chen, Y. (2018) · Lecture notes in computer science · doi:10.1007/978-3-030-05051-1_24 · Cited by 5
Recognizing Bellman–Ford-Orderable Graphs
Haddad, R. W., & Schäffer, A. A. (1988) · SIAM Journal on Discrete Mathematics · doi:10.1137/0401045 · Cited by 5
Assignment techniques on Virtual Networks Performance considerations on large multi-modal networksPreprint
Jourquin, B., & Limbourg, S. (2003) · RePEc: Research Papers in Economics · doi:10.13140/2.1.3905.6644 · Cited by 5
Average-case complexity of shortest-paths problems
Priebe, V. (2001) · Max Planck Institute for Plasma Physics · doi:10.22028/d291-25863 · Cited by 5
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.