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 <jgoerzen@complete.org>
 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.