#### Previous topic

Basic Plotting with Matplotlib

#### Next topic

Application: Finite State Optimal Growth

# Application: Shortest Paths and Dynamic Programming¶

Here’s a little application concerning how to find the shortest paths on a graph

• This is a well-known problem

• Applications in
• Finding directions between locations
• Operations research, robotics, etc.
• A simple example of dynamic programming, which is one of our key topics

## Outline of the Problem¶

Consider the following graph

We are interested in getting from node (vertex) A to node G at minimum cost

Arrows (edges) indicate the movements we can take

Numbers next to edges indicate the cost of traveling that edge

Possible interpretations

• Minimum cost for supplier to reach a destination
• Routing of packets on the internet (minimize time)

A quick scan of the edges shows that the optimal paths are

• A, C, F, G at cost 8
• A, D, F, G at cost 8

## Finding Least-Cost Paths¶

For large graphs we need a systematic solution

Let $$J(v)$$ denote the minimum cost-to-go from node $$v$$

• Total cost from $$v$$ if we take the best route

Suppose that we know $$J(v)$$ for each node $$v$$

Note that $$J(G) = 0$$

Intuitively, the best path can now be found as follows

• Start at A
• From node v, move to any node that solves
(1)$\min_{w \in F_v} \{ c(v, w) + J(w) \}$

where

• $$F_v$$ is the set of nodes which can be reached from $$v$$ in one step
• $$c(v, w)$$ is the cost of traveling from $$v$$ to $$w$$

Hence, if we know the function $$J$$, then finding the best path is trivial

But how to find $$J$$?

Some thought will convince you that, for every node $$v$$, the function $$J$$ satisfies

(2)$J(v) = \min_{w \in F_v} \{ c(v, w) + J(w) \}$

This is known as Bellman’s equation

• That is, $$J$$ is the solution to Bellman’s equation
• There are algorithms for finding this solution

## Solving for $$J$$¶

The standard algorithm for finding $$J$$ is to start with

(3)$J_0(v) = M \text{ if } v \not= \text{ destination, else } J_0(v) = 0$

where M is a big number

Now we use the following algorithm

1. Set $$n = 0$$
2. Set
(4)$J_{n+1} (v) = \min_{w \in F_v} \{ c(v, w) + J_n(w) \} \qquad \text{ for all } v$
1. If $$J_{n+1}$$ and $$J_n$$ are not equal then increment $$n$$, go to 2

In general, this sequence converges to $$J$$—the proof is omitted

### Exercises¶

Use this algorithm to find the optimal path (and its cost) for this graph

Here the line

node0, node1 0.04, node8 11.11, node14 72.21

means that from node0 we can go to

• node1 at cost 0.04
• node8 at cost 11.11
• node14 at cost 72.21

And so on, and so on

According to my calucations, the path and is cost are like this

### Solution¶

## Filename: shortpath.py
## John Stachurski, July 2009

""" Read in the graph from the data file.  The graph is stored
as a dictionary, where the keys are the nodes, and the values
are a list of pairs (d, c), where d is a node and c is a number.
If (d, c) is in the list for node n, then d can be reached from
n at cost c.
"""
graph = {}
infile = open('graph.txt')
for line in infile:
elements = line.split(',')
node = elements.pop(0).strip()
graph[node] = []
if node != 'node99':
for element in elements:
destination, cost = element.split()
graph[node].append((destination.strip(), float(cost)))
infile.close()
return graph

def update_J(J, graph):
"The Bellman operator."
next_J = {}
for node in graph:
if node == 'node99':
next_J[node] = 0
else:
next_J[node] = min(cost + J[dest] for dest, cost in graph[node])
return next_J

def print_best_path(J, graph):
""" Given a cost-to-go function, computes the best path.  At each node n,
the function prints the current location, looks at all nodes that can be
reached from n, and moves to the node m which minimizes c + J[m], where c
is the cost of moving to m.
"""
sum_costs = 0
current_location = 'node0'
while current_location != 'node99':
print current_location
running_min = 1e100  # Any big number
for destination, cost in graph[current_location]:
cost_of_path = cost + J[destination]
if cost_of_path < running_min:
running_min = cost_of_path
minimizer_cost = cost
minimizer_dest = destination
current_location = minimizer_dest
sum_costs += minimizer_cost

print 'node99'
print
print 'Cost: ', sum_costs

## Main loop

M = 1e10
J = {}
for node in graph:
J[node] = M
J['node99'] = 0

while 1:
next_J = update_J(J, graph)
if next_J == J:
break
else:
J = next_J
print_best_path(J, graph)