Aduke.1638
net.general
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