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
On the History of Combinatorial Optimization (Till 1960)
Schrijver, A. (2005) · Handbooks in Operations Research and Management Science · doi:10.1016/s0927-0507(05)12001-5 · Cited by 241
Freight transportation demand elasticities: a geographic multimodal transportation network analysis
Beuthe, M., Jourquin, B., Geerts, J.-F., & Ha, C. K. A. N. (2001) · Transportation Research Part E Logistics and Transportation Review · doi:10.1016/s1366-5545(00)00022-3 · Cited by 228
Even, S. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9781139015165 · Cited by 218
Overview of Path-Planning and Obstacle Avoidance Algorithms for UAVs: A Comparative Study
Radmanesh, M., Kumar, M., Guentert, P. H., & Sarim, M. (2018) · Unmanned Systems · doi:10.1142/s2301385018400022 · Cited by 217
Shortest-Route Methods: 1. Reaching, Pruning, and Buckets
Denardo, E. V., & Fox, B. L. (1979) · Operations Research · doi:10.1287/opre.27.1.161 · Cited by 198
Exact and approximate reasoning about temporal relations1
Van Beek, P., & Cohen, R. (1990) · Computational Intelligence · doi:10.1111/j.1467-8640.1990.tb00130.x · Cited by 196
The Shortest Path Problem Revisited: Optimal Routing for Electric Vehicles
Artmeier, A., Haselmayr, J., Leucker, M., & Sachenbacher, M. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-16111-7_35 · Cited by 189
Optimal Route Planning for Electric Vehicles in Large Networks
Eisner, J., Funke, S., & Storandt, S. (2011) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v25i1.7991 · Cited by 184
Shortest‐path methods: Complexity, interrelations and new propositions
Pallottino, S. (1984) · Networks · doi:10.1002/net.3230140206 · Cited by 179
On the complexity of admissible search algorithms
Martelli, A. (1977) · Artificial Intelligence · doi:10.1016/0004-3702(77)90002-9 · Cited by 178
Shortest path methods: A unifying approach
Gallo, G., & Pallottino, S. (1986) · Mathematical programming studies · doi:10.1007/bfb0121087 · Cited by 161
Kang, J., Michels, A., Lyu, F., Wang, S., Agbodo, N., Freeman, V. L., & Wang, S. (2020) · International Journal of Health Geographics · doi:10.1186/s12942-020-00229-x · Cited by 150
Another adaptive distributed shortest path algorithm
Humblet, P. A. (1991) · IEEE Transactions on Communications · doi:10.1109/26.87189 · Cited by 125
Jourquin, B., & Beuthe, M. (1996) · Transportation Research Part C Emerging Technologies · doi:10.1016/s0968-090x(96)00019-8 · Cited by 123
Approximation algorithms for temporal reasoning
van Beek, P. (1989) · International Joint Conference on Artificial Intelligence · Cited by 119
An adaptive genetic algorithm for robot motion planning in 2D complex environments
Karami, A. H., & Hasanzadeh, M. (2015) · Computers & Electrical Engineering · doi:10.1016/j.compeleceng.2014.12.014 · Cited by 112
A cross-layer communication module for the Internet of Things
Han, C. Z., Jornet, J. M., Fadel, E. A., & Akyildiz, I. F. (2012) · Computer Networks · doi:10.1016/j.comnet.2012.10.003 · Cited by 112
A heuristic search algorithm with modifiable estimate
Mérő, L. (1984) · Artificial Intelligence · doi:10.1016/0004-3702(84)90003-1 · Cited by 112
Biomedical Event Extraction based on Knowledge-driven Tree-LSTM
Li, D., Huang, L., Ji, H., & Han, J. (2019) · Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT) · doi:10.18653/v1/n19-1145 · Cited by 99
Wang, Y., & You, S.-Y. (2018) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2018.2872054 · Cited by 94
Xing, L., & Perelman, L. (2022) · Journal of Water Resources Planning and Management · doi:10.1061/(asce)wr.1943-5452.0001550 · Cited by 91
A Star Search Algorithm for Civil UAV Path Planning with 3G Communication
Tseng, F., Liang, T.-T., Lee, C. H., Chou, L. D., & Chao, H. C. (2014) · International Conference on Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP) · doi:10.1109/iih-msp.2014.236 · Cited by 90
Trajectory planning for UAV navigation in dynamic environments with matrix alignment Dijkstra
Wang, J., Li, Y., Li, R., Chen, H., & Chu, K. (2022) · Soft Computing · doi:10.1007/s00500-022-07224-3 · Cited by 87
Privacy-Preserving Real-Time Navigation System Using Vehicular Crowdsourcing
Ni, J., Lin, X., Zhang, K., & Shen, X. (2016) · IEEE Vehicular Technology Conference · doi:10.1109/vtcfall.2016.7881177 · Cited by 83
The optimal routing problem in the context of battery-powered electric vehicles
Artmeier, J. H. A., & Sachenbacher, M. (2010) · mediaTUM (Technical University of Munich) · Cited by 77
Hybrid Bellman–Ford–Dijkstra algorithm
Dinitz, Y., & Itzhak, R. (2017) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2017.01.001 · Cited by 75
Inland Waterway Ship Path Planning Based on Improved RRT Algorithm
Cao, S., Fan, P., Yan, T., Xie, C. J., Deng, J., Xu, F. Z., & Shu, Y. (2022) · Journal of Marine Science and Engineering · doi:10.3390/jmse10101460 · Cited by 73
Deadlock-Free Oblivious Routing for Arbitrary Topologies
Domke, J., Hoefler, T., & Nagel, W. E. (2011) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2011.65 · Cited by 72
Quality of Service Routing in the Internet: Theory, Complexity and Algorithms
Kuipers, F. A. (2004) · Research Repository (Delft University of Technology) · Cited by 72
Li, Y., Jin, R., & Luo, Y. (2018) · Journal of the American Medical Informatics Association · doi:10.1093/jamia/ocy157 · Cited by 69
GraphCrop: Subgraph Cropping for Graph ClassificationPreprint
Wang, Y., Wang, W., Liang, Y., Cai, Y., & Hooi, B. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.10564 · Cited by 67
Controller placement problem in software‐defined networking: A survey
Kumari, A., & Sairam, A. S. (2021) · Networks · doi:10.1002/net.22016 · Cited by 64
Dong, F., Zhang, S., Shi, X., Wu, H., & Tan, C. (2021) · IEEE Transactions on Instrumentation and Measurement · doi:10.1109/tim.2021.3089767 · Cited by 61
Chang, I.-C., Tai, H.-T., Yeh, F.-H., Hsieh, D.-L., & Chang, S.-H. (2013) · International Journal of Distributed Sensor Networks · doi:10.1155/2013/794521 · Cited by 57
Building a large-scale and wide-area quantum Internet based on an OSI-alike model
Li, Z., Xue, K., Li, J., Yu, N., Liu, J., Wei, D. S. L., Sun, Q., & Lu, J. (2021) · China Communications · doi:10.23919/jcc.2021.10.001 · Cited by 55
Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles
Baum, M., Dibbelt, J., Wagner, D., & Zündorf, T. (2020) · Transportation Science · doi:10.1287/trsc.2020.0981 · Cited by 54
The Application of Graph in BIM/GIS Integration
Zhu, J., Chong, H., Zhao, H., Wu, J., Tan, Y., & Xu, H. (2022) · Buildings · doi:10.3390/buildings12122162 · Cited by 54
Graph-Theory-Based Derivation, Modeling, and Control of Power Converter Systems
Li, Y., Kuprat, J., Li, Y., & Liserre, M. (2022) · IEEE Journal of Emerging and Selected Topics in Power Electronics · doi:10.1109/jestpe.2022.3143437 · Cited by 53
Origin-Destination Travel Time Oracle for Map-based Services
Lin, Y. D., Wan, H., Hu, J., Guo, S., Yang, B., Lin, Y., & Jensen, C. S. (2023) · Proceedings of the ACM on Management of Data · doi:10.1145/3617337 · Cited by 52
Adaptive Routing of Cruising Taxis by Mutual Exchange of Pathways
Yamamoto, K., Uesugi, K., & Watanabe, T. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85565-1_69 · Cited by 51
A Survey of Analysis Techniques for Discrete Algorithms
Weide, B. W. (1977) · ACM Computing Surveys · doi:10.1145/356707.356711 · Cited by 51
Composite Travel Generative Adversarial Networks for Tabular and Sequential Population Synthesis
Badu-Marfo, G., Farooq, B., & Patterson, Z. (2022) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2022.3168232 · Cited by 50
Privacy-preserving Navigation Supporting Similar Queries in Vehicular Networks
Li, M., Chen, Y., Zheng, S., Hu, D., Lal, C., & Conti, M. (2020) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2020.3017534 · Cited by 47
Lu, B., Li, B., Chen, W., Jin, Y., Zhao, Z., Dou, Q., Heng, P., & Liu, Y. (2021) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2021.3136185 · Cited by 46
Dao, T.-K., Ngo, T.-G., Pan, J., Nguyen, T.-T.-T., & Nguyen, T.-T. (2024) · Biomimetics · doi:10.3390/biomimetics9010035 · Cited by 44
Hybrid multiple attribute group decision-making for power system restoration
Sun, P., Liu, Y., Qiu, X., & Wang, L. (2015) · Expert Systems with Applications · doi:10.1016/j.eswa.2015.05.001 · Cited by 43
Bình, H. T. T., Thành, P. Đ., & Thang, T. B. (2019) · Knowledge-Based Systems · doi:10.1016/j.knosys.2019.05.015 · Cited by 43
Properties of Labeling Methods for Determining Shortest Path Trees
Shier, D. R., & Witzgall, C. (1981) · Journal of Research of the National Bureau of Standards · doi:10.6028/jres.086.013 · Cited by 43
Optimization based routing model for the dynamic path planning of emergency vehicles
Jose, C., & Grace, K. S. V. (2020) · Evolutionary Intelligence · doi:10.1007/s12065-020-00448-y · Cited by 42
Exact and approximate reasoning about qualitative temporal relations
van Beek, P. (1992) · Cited by 42
Rafiq, A., Afaq, M., & Song, W. (2020) · Journal of Ambient Intelligence and Humanized Computing · doi:10.1007/s12652-020-01753-1 · Cited by 41
Energy-Optimal Routes for Battery Electric Vehicles
Baum, M., Dibbelt, J., Pajor, T., Sauer, J., Wagner, D., & Zündorf, T. (2019) · Algorithmica · doi:10.1007/s00453-019-00655-9 · Cited by 39
Ayub, S., Ayob, S. M., Tan, C. W., Ayub, L., & Bukar, A. L. (2020) · Sustainable Energy Technologies and Assessments · doi:10.1016/j.seta.2020.100798 · Cited by 39
A Random Forest Model for Travel Mode Identification Based on Mobile Phone Signaling Data
Lu, Z., Long, Z., Xia, J., & An, C. (2019) · Sustainability · doi:10.3390/su11215950 · Cited by 39
Wireless Mobile-Based Shopping Mall Car Parking System (WMCPS)
Khang, S. C., Hong, T. J., Chin, T. S., & Wang, S. (2010) · IEEE Asia-Pacific Services Computing Conference (APSCC) · doi:10.1109/apscc.2010.116 · Cited by 39
Men, J., Chen, G., Zhou, L., & Chen, P. (2022) · Process Safety and Environmental Protection · doi:10.1016/j.psep.2022.03.048 · Cited by 38
A Reinforcement Learning Routing Protocol for UAV Aided Public Safety Networks
Minhas, H. I., Ahmad, R., Ahmed, W., Waheed, M., Alam, M. M., & Gul, S. T. (2021) · Sensors · doi:10.3390/s21124121 · Cited by 37
On the privacy protection of indoor location dataset using anonymization
Fathalizadeh, A., Moghtadaiee, V., & Alishahi, M. (2022) · Computers & Security · doi:10.1016/j.cose.2022.102665 · Cited by 37
Electric Vehicle Routing with Realistic Recharging Models
Zündorf, T. (2014) · Cited by 36
León, J., & March, A. (2016) · International Planning Studies · doi:10.1080/13563475.2016.1234368 · Cited by 35
PINC: Pickup Non-Critical Node Based k-Connectivity Restoration in Wireless Sensor Networks
Akram, V. K., Dağdevıren, Z. A., Dağdevıren, O., & Challenger, M. (2021) · Sensors · doi:10.3390/s21196418 · Cited by 35
Smell Detection Agent Based Optimization Algorithm
S, V. C. S. (2015) · Journal of The Institution of Engineers (India) Series B · doi:10.1007/s40031-014-0182-0 · Cited by 34
Latency-Efficient VNF Deployment and Path Routing for Reliable Service Chain
Chen, Y., & Wu, J. (2020) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2020.3048033 · Cited by 32
Elgendy, M. A., Sik‐Lányi, C., & Kelemen, A. (2021) · Computer Methods and Programs in Biomedicine · doi:10.1016/j.cmpb.2021.106112 · Cited by 31
Dowson, N., Boult, M., Cowled, P., de Loryn, T., & Fitridge, R. (2014) · European Journal of Vascular and Endovascular Surgery · doi:10.1016/j.ejvs.2014.04.033 · Cited by 31
Shortest-path queries on complex networks: experiments, analyses, and improvement
Zhang, J., Li, W., Yuan, L., Qin, L., Zhang, Y., & Chang, L. (2022) · Proceedings of the VLDB Endowment · doi:10.14778/3551793.3551820 · Cited by 30
A simulation-based optimization approach for designing transit networks
Nnene, O. A., Joubert, J. W., & Zuidgeest, M. H. P. (2023) · Public Transport · doi:10.1007/s12469-022-00312-5 · Cited by 30
Distributed computation of node and edge betweenness on tree graphs
Wang, W., & Tang, C. Y. (2013) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2013.6759856 · Cited by 30
A method for computing heuristics in problem solving
Guida, G., & Somalvico, M. (1979) · Information Sciences · doi:10.1016/0020-0255(79)90024-0 · Cited by 30
Novel Approach Sizing and Routing of Wireless Sensor Networks for Applications in Smart Cities
Inga, E., Inga, J., & Ortega, A. (2021) · Sensors · doi:10.3390/s21144692 · Cited by 29
Naderi, S., Javadi, M., Mazhari, M., & Chung, C. Y. (2022) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2022.3165210 · Cited by 29
Dynamic energy efficient routing protocol in wireless sensor networks
Haque, M. E., & Baroudi, U. A. (2020) · Wireless Networks · doi:10.1007/s11276-020-02290-7 · Cited by 29
I/O-efficiency of shortest path algorithms: an analysis
Jiang, B. (2003) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.1992.213212 · Cited by 29
Deep Learning with Skip Connection Attention for Choroid Layer Segmentation in OCT Images
Mao, X., Zhao, Y., Chen, B., Ma, Y., Gu, Z., Gu, S., Yang, J., Cheng, J. T., & Liu, J. (2020) · Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC) · doi:10.1109/embc44109.2020.9175631 · Cited by 27
Kazazi, A. K., Amiri, F., Rahmani, Y., Samouei, R., & Rabiei‐Dastjerdi, H. (2022) · Sustainability · doi:10.3390/su142114106 · Cited by 27
Transient stability assessment using artificial neural networks
El-Amin, I. M., & Al-Shams, A.-A. M. (1997) · Electric Power Systems Research · doi:10.1016/s0378-7796(96)01124-8 · Cited by 27
Chen, D., Wang, Z., Zhou, G., & Li, S. (2022) · Sustainability · doi:10.3390/su142215137 · Cited by 26
The influence of random interactions and decision heuristics on norm evolution in social networks
Mungovan, D., Howley, E., & Duggan, J. (2011) · Computational and Mathematical Organization Theory · doi:10.1007/s10588-011-9085-7 · Cited by 26
Context-Aware Architecture for Probabilistic Voting-based Filtering Scheme in Sensor Networks
Nam, S. M., & Cho, T. H. (2016) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2016.2641219 · Cited by 24
Consumption Profiles in Route Planning for Electric Vehicles: Theory and Applications
Baum, M., Sauer, J., Wagner, D., & Zündorf, T. (2017) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.sea.2017.19 · Cited by 24
Liver DCE-MRI Registration in Manifold Space Based on Robust Principal Component Analysis
Feng, Q., Zhou, Y., Li, X., Mei, Y., Lu, Z., Zhang, Y., Feng, Y., Liu, Y., Yang, W., & Chen, W. (2016) · Scientific Reports · doi:10.1038/srep34461 · Cited by 23
Nhu, H. T. T., Drigo, R. A. E., Berggren, P., & Boudier, T. (2017) · Scientific Reports · doi:10.1038/srep44261 · Cited by 23
Jourquin, B., & Limbourg, S. (2006) · European journal of transport and infrastructure research · doi:10.18757/ejtir.2006.6.3.3446 · Cited by 23
Understanding the mobility of public transport systems based on weighted multiplex networks
Li, Z., Chen, Y., Tang, J., Zhu, K., & Pan, X. (2023) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2023.128977 · Cited by 22
DEA‐based centralized resource allocation with network flows
Tao, X., Xiong, B., & An, Q. (2020) · International Transactions in Operational Research · doi:10.1111/itor.12845 · Cited by 22
City-Scale Grid-Topological Hybrid Maps for Autonomous Mobile Robot Navigation in Urban Area
Niijima, S., Umeyama, R., Sasaki, Y., & Mizoguchi, H. (2020) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros45743.2020.9340990 · Cited by 21
Functional Split-Aware Optimal BBU Placement for 5G Cloud-RAN Over WDM Access/Aggregation Network
Ahsan, M. H., Ahmed, A., Al‐Dweik, A., & Ahmad, A. (2022) · IEEE Systems Journal · doi:10.1109/jsyst.2022.3150468 · Cited by 21
Jia, J., Chen, Y., Wang, Y., Li, T., & Li, Y. (2020) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2020.125578 · Cited by 21
Zhang, A., Zhen, Q., Zheng, C., Li, J., Zheng, Y., Du, Y., Huang, Q., & Zhang, Q. (2023) · Journal of Building Engineering · doi:10.1016/j.jobe.2023.106807 · Cited by 20
Gao, M., Li, Z., Li, R., Cui, C.-H., Chen, X., Ye, B., Li, Y., Gu, W., Gong, Q., Wang, X., et al. (2023) · Patterns · doi:10.1016/j.patter.2023.100839 · Cited by 20
Path Merging Based Betweenness Centrality Algorithm in Delay Tolerant Networks
Zheng, Z., Du, B., Zhao, C. X., & Xie, P. (2023) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2023.3310071 · Cited by 20
E2E network slice management framework for 5G multi-tenant networks
Chirivella‐Perez, E., Salvá-García, P., Sanchez-Navarro, I., Calero, J. M. A., & Wang, Q. (2023) · Journal of Communications and Networks · doi:10.23919/jcn.2023.000019 · Cited by 20
Implementasi Algoritma Dijkstra untuk Menentukan Rute Terpendek Menuju Pelayanan Kesehatan
Wulandari, I. A., & Sukmasetyan, P. (2022) · Jurnal Ilmiah Sistem Informasi (JISI) · doi:10.24127/jisi.v1i1.1953 · Cited by 19
Efficient Network Slicing for 5G Services in Cloud Fog-RAN Deployment Over WDM Network
Ahsan, M. H., Ahmed, A., Fida, H., Al‐Dweik, A., Hashmi, U. S., & Ahmad, A. (2023) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2023.3266234 · Cited by 19
Li, R., Zhang, P., Yin, Z., & Sheil, B. B. (2024) · International Journal for Numerical and Analytical Methods in Geomechanics · doi:10.1002/nag.3832 · Cited by 19
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.