Aeagle.179
net.general
utcsrgv!utzoo!decvax!ucbvax!ihnss!eagle!cw
Wed Jan 13 10:03:47 1982
"Dijkstra and the USENET map"
Perhaps I am missing the point, but if the problem is simply to find the
shortest path between two nodes (assuming some simple cost function such
as the first branch out of any node is always cheapest), why can't
a shortest path algorithm (like Dijkstra) be run for every pair of nodes?
Roughly n**3 time in a stupid implementation--better ways probably exist.
Notice that the paths need not be symmetric; there might be one-way edges
or edges with different costs in the two directions.
-----------------------------------------------------------------
gopher://quux.org/ conversion by John Goerzen
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.