In the shortest route problem, we want to find the shortest distance from point A to point B in a network.

We will use an approach called dynamic programming (DP) to solve this problem. Dynamic programming involves breaking a large, difficult problem up into a series of smaller, more manageable problems. By solving the series of smaller problems, we are able to construct the solution to the initial large problem. Typically, the most difficult aspect of DP is not the mathematics involved in solving the smaller subproblems, but coming up with a scheme, or recursion, for decomposing the problem.

To find the distance of the shortest path through the network, we will use the following DP recursion:

F( i) = min [ D( i, j) + F( j)]

           j

where F( i) is the minimal travel distance from point i to the final destination point and D( i, j) is the distance from point i to point j. In words, the minimal distance from node i to the terminal node is the minimum over all points reachable along a single arc from i of the sum of the distance from i to the adjoining node plus the minimal distance from the adjoining node to the terminal node.