Perhaps the simplest scenario to which a dynamic-programming solution is applicable is that of finding the shortest path between a given pair of nodes in a network. We will use this scenario to illustrate in detail the concepts involved in formulating and solving a problem by dynamic programming.

Suppose we are interested in traveling (by car) from San Francisco to New York. Suppose further that the possible routes along with the actual mileages between cities are as specified in the network below.

Notice that in this network every arc between two cities is "directed"; this means that we can only travel in the indicated left-to-right (or west-to-east) direction. Such a network is called a directed network.

Given the above network, the problem of interest is to determine the shortest travel distance between San Francisco and New York. We shall refer to a problem of this type as an elementary path problem. At the next link, we will provide a solution of this problem by dynamic programming.

The Elementary Path Problem: Solution by Dynamic Programming

The discussion of the elementary path problem refers to several figures. To view these figures, click on the following titles: Figure DP-2, Figure DP-3, Figure DP-4.

Our formulation and solution of the elementary path problem can be implemented in Excel. This is provided here: The Elementary Path Problem - Excel Implementation. It is interesting to note that once the dynamic-programming solution is implemented in Excel, we can conduct sensitivity analysis using the "datatable" feature in Excel.

Finally, note that our notation is slightly different from that in the text. A general rule of thumb is that: We use i to denote possible states, whereas the text uses s; we use V(i) to denote an optimal value, whereas the text uses f^*(s). Pages 540 and 541 in the text provides a summary of their notation.