Accession Number : ADA322745

Title :   Scaling Algorithms for the Shortest Paths Problem,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Goldberg, Andrew

PDF Url : ADA322745

Report Date : MAY 1992

Pagination or Media Count : 15

Abstract : We give an O((square root of n)m log N) algorithm for the single-source shortest paths problem with integral arc lengths. (Here n and m is the number of nodes and arcs in the input network and N is essentially the absolute value of the most negative arc length.) This improves previous bounds for the problem.

Descriptors :   *ALGORITHMS, OPTIMIZATION, INPUT OUTPUT PROCESSING, SCALING FACTOR, SUBROUTINES.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE