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 <
[email protected]>
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.
