Amitccc.103
net.general
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