Aeagle.179
net.general
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.