On the Shortest Route Through a Network

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.

• 저널Management Science · 6(2) · 187–190
• 토픽Data Management and Algorithms · Signal Processing
• DOI10.1287/mnsc.6.2.187
• 저자George B. Dantzig