Aduke.1638
net.general
utcsrgv!utzoo!decvax!duke!trt
Mon Jan 18 23:11:04 1982
Re: mitccc.103: Re: "Dijkstra and the USENET map"
Problem: Compute the shortest path between node S and node X of a
directed graph of N nodes and E edges with nonnegative integer costs.
Dijkstra's algorithm solves this in O(N^2) steps,
fast enough for Usenet, but not necessarily optimal.
unc!smb has such a router, and is looking for cost functions.
Robert Wagner (duke!raw) has an O(max(N + E + D)) algorithm,
where D is the length of the shortest path found.
It uses a bucket sort, and works best if edge costs are small integers.
Reference: "Shortest Path Algorithm for Edge-Sparse Graphs",
JACM Vol. 23, No. 1, Jan 1976, pp. 50-57
-----------------------------------------------------------------
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.
