Shortest Paths

Overview

The shortest path problem is a classic problem in mathematics and computer science with applications in

  • Economics (sequential decision making, analysis of social networks, etc.)
  • Operations research and transportation
  • Robotics and artificial intelligence
  • Telecommunication network design and routing
  • etc., etc.

Variations of the methods we discuss in this lecture are used millions of times every day, in applications such as

  • Google Maps
  • routing packets on the internet

For us, the shortest path problem also provides a nice introduction to the logic of dynamic programming

Dynamic programming is an extremely powerful optimization technique that we apply in many lectures on this site

Outline of the Problem

The shortest path problem is one of finding how to traverse a graph from one specified node to another at minimum cost

Consider the following graph

../_images/graph.png

We wish to travel 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 of the graph include

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

For this simple graph, 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\), understood as the total cost from \(v\) if we take the best route

Suppose that we know \(J(v)\) for each node \(v\), as shown below for the graph from the preceding example

../_images/graph2.png

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 that 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 almost 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 the Bellman equation

  • That is, \(J\) is the solution to the Bellman equation
  • There are algorithms for computing the minimum cost-to-go function \(J\)

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 some large number

Now we use the following algorithm

  1. Set \(n = 0\)
  2. Set \(J_{n+1} (v) = \min_{w \in F_v} \{ c(v, w) + J_n(w) \}\) 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

Exercise 1

Use the algorithm given above 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

According to our calculations, the optimal path and its cost are like this

Your code should replicate this result