On the Shortest Route through a Network
Abstract
The chief feature of the method is that it fans out from the origin working out the shortest path to one new node from the origin and never having to backtrack. No more than n(n-1)/2 comparisons are needed to find the shortest route from a given origin to all other nodes and possibly less between two fixed nodes. Except for details and bias of various authors towards a particular brand of proof, this problem has been solved the same way by many authors. This paper refines these proposals to give what is believed to be the shortest procedure for finding the shortest route when it is little effort to arrange distances in increasing order by nodes or to skip consideration of arcs into nodes whose shortest route to the origin has been determined earlier in the computation. In practice the number of comparisons is much less than indicated bounds because all arcs leading to nodes previously evaluated are deleted from further consideration. A further efficiency can be achieved in the event of ties by including least distances from origin to many nodes simultaneously during the fanning out process. However, these are shown as separate steps to illustrate the underlying principle.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 29, 1959
- Accession Number
- AD0606903
Entities
People
- George Bernard Dantzig
Organizations
- RAND Corporation