1972•Unpublished venueRequires access
On shortest paths and sorting
Ellis L. Johnson
Open publisher page 41 citations
Abstract
In finding shortest paths, the operation of finding, successively, a minimum from a list of numbers may require more work than the remainder of the algorithm. It is shown how algorithms from sorting literature can be used to accomplish this part of the shortest path algorithm. Bounds on the largest possible amount of work are established, and results of a computational study are reported.