A Note on Dijkstra's Shortest Path Algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Note on Dijkstra's Shortest Path Algorithm

Full text

Pdf (253 KB)

Source

Journal of the ACM (JACM) archive
Volume 20 , Issue 3 (July 1973) table of contents

Pages: 385 - 388

Year of Publication: 1973

ISSN:0004-5411

Author

Donald B. Johnson

Department of Computer Science, Cornell University, Ithaca, New York

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 47, Downloads (12 Months): 268, Citation Count: 4

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321765.321768 What is a DOI?

ABSTRACT

An assertion that Dijkstra's algorithm for shortest paths (adapted to allow arcs of negative weight) runs in O(n3) steps is disproved by showing a set of networks which take O(n2n) steps.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	DIJKSTRA, E W. A note on two problems in connexion with graphs. Numer. Math. 1 (1959), 269-271.
	2	Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
	3	Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]

CITED BY 4

	Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977
	Bruce Weide, A Survey of Analysis Techniques for Discrete Algorithms, ACM Computing Surveys (CSUR), v.9 n.4, p.291-313, Dec. 1977
	Nighat Yasmin, Incremental computation of shortest paths in semi-dynamic graphs using software components, Proceedings of the 44th annual southeast regional conference, March 10-12, 2006, Melbourne, Florida
	Peter Van Beek, Approximation algorithms for temporal reasoning, Proceedings of the 11th international joint conference on Artificial intelligence, p.1291-1296, August 20-25, 1989, Detroit, Michigan