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\]

3. 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

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)