Amitccc.103
net.general
utcsrgv!utzoo!decvax!ucbvax!mhtsa!alice!mitccc!jfw
Fri Jan 15 17:46:36 1982
Re: "Dijkstra and the USENET map"
The Dijkstra algorithm is O(n^2), given the limitation that edges are all of
positive weight.  There is a generalized algorithm, by Warshall, which is
O(n^3) for any graph, needing hooks to watch out for negative cycles.
O(n^2) is considered a fairly obvious minimum, since for each edge, one must
consider how far each other edge is away...
	-John Woods (woods@ll-asg, eagle!mitccc!jfw),
		recent victim of 6.046 Computer.Algorithms@MIT

-----------------------------------------------------------------
 gopher://quux.org/ conversion by John Goerzen <jgoerzen@complete.org>
 of http://communication.ucsd.edu/A-News/


This Usenet Oldnews Archive
article may be copied and distributed freely, provided:

1. There is no money collected for the text(s) of the articles.

2. The following notice remains appended to each copy:

The Usenet Oldnews Archive: Compilation Copyright (C) 1981, 1996 
 Bruce Jones, Henry Spencer, David Wiseman.