Finding the Shortest Route between Two Points in a Network

TLDR

The technique has applications to scheduling and other problems. The authors propose a new method for finding the shortest route between two points in an interconnected network. The method iteratively explores routes from both ends, extending the shortest partial routes until a complete path is found and verified as minimal. The new method is more efficient than alternative linear or dynamic programming approaches.

Abstract

A new method is proposed for finding the shortest route between two points in an interconnected network. The shortest route is found by investigating a selection of routes from both the starting point and the terminal point. The selection of routes is decided dynamically by extending one by one the routes which have currently covered the least distance. Once a complete through route has been found, it has to be made certain that it is the minimum. The new method appears to be more efficient than alternative approaches to the problem through linear or dynamic programming. Some applications of the technique to scheduling and other problems are briefly described.