1  Shortest Paths

Perhaps the most basic example of a problem that is set up for solution by dynamic programming is the shortest path problem. That is, find the shortest path through a network. Google Maps does this for you when you seek driving directions from point A to point B. Here is an example from the text.
fig2-3.png

Here is a link to R code that will solve the shortest path problem. Comments are indicated by #. In other words, anything that follows a # sign is a comment and not part of the code.
short_path.r short_path.r
The above code reads the data on the path length between nodes from a table contained in a file (in the same directory that was used to open R) . The file name is net.txt and can be seen here.
net.txt net.txt
The above code does not keep track of the path that gives the optimal solution. Here is a second bit of code that computes the optimal solution, finds the optimal path, and gives the optimal next node starting at any node.
short_path2.r short_path2.r

File translated from TEX by TTM, version 3.72.
On 18 Jan 2007, 09:37.