Consider a phone network. At any given time, a message may take a certain amount of time to traverse each line (due to congestion effects, switching delays, and so on). This time can vary greatly minute by minute and telecommunication companies spend a lot of time and money tracking these delays and communicating these delays throughout the system. Assuming a centralized switcher knows these delays, there remains the problem of routing a call so as to minimize the delays. So, in figure 1, what is the least delay path from LA to Boston? How can we find that path quickly?

This is an example of a particular type of network model, called the
*shortest path problem*. In such a problem, you have a network
with costs on the edges and two special nodes: a start node and a
finish node. The goal is to find a path from the start node to the
finish node whose total weight is minimized.

Here is another problem that might not appear to be a shortest path problem, but really is:

At a small but growing airport, the local airline
company is purchasing a new tractor for a tractor-trailer train to
bring luggage to and from the airplanes. A new mechanized luggage
system will be installed in 3 years, so the tractor will not be needed
after that. However, because it will receive heavy use, and
maintenance costs are high, it may still be more economical to replace
the tractor after 1 or 2 years. The following table gives the total
net discounted cost associated with purchasing a tractor in year *i*
and trading it in in year *j* (where year 0 is now):

The problem is to determine at what times the tractor should be replaced (if ever) to minimize the total costs for tractors. How can this be formulated as a shortest path problem?

Sun Jun 14 13:20:08 EDT 1998