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
- See the Wikipedia entry
- 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
where
- Fv 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 J, then finding the best path is trivial
But how to find J?
A little thought will convince you that, for every node v, the function J satisfies
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
where M is a big number
Now we use the following algorithm
- Set n = 0
- Set
- If Jn+1 and Jn 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
def read_graph():
""" 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
graph = read_graph()
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)
0 comments:
Post a Comment