Branch & Bound Network Optimisation Models The shortest path problem

Imagine you are given a road map and asked to find the shortest route between two points on the map. For very simple maps you can often do this just by looking at the map, but if the map looks more like a bunch of spaghetti thrown against the wall you're going to need a better method. This is actually a very important problem; services like Google Maps or MapQuest are entirely concerned with answering this problem. One way of finding the shortest path between two locations is Dijkstra's algorithm (DIKE-stra). In fact we will see that this algorithm does one better, and can actually find the shortest path from the starting location to any other location, not just the desired destination.

Setup

Since roads come in varying lengths we want to work on weighted graphs for this problem. A weighted graph is simply a graph where each edge e is assigned a non-negative value called the weight, w(e), of the edge. A path is a sequence of vertices p = (v₁,...,v_n) such that v_i ~ v_i+1. Set e_i = (v_i,v_i+1). The length of a path p is d(p) = &Sigma w(e_i). For convenience we will also write w(u,v) to denote the weight of the edge (u,v).

The Algorithm

The idea behind Dijkstra's algorithm is breadth-first search (BFS). This type of search explores vertices by spreading out as new vertices are found. This is akin to starting a fire on the graph. We light the starting vertex, and then the fire spreads to its neighbors while going out at the starting node. The fire then spreads to the unburned neighbors of the burning vertices, and so on until the entire graph is burned. For our purpose we will assume that only one vertex can be burning at a time; that is our fire will always choose to spread to the closest neighbor.

Pick a starting vertex o. We label each vertex v in the graph with a "distance" δ(v) from o. We start out with δ(o) = 0 and guess ∞ for the rest. We start with each vertex in the Unburned state, from which we will remove them as they are burned by the algorithm. Removed nodes are called Burned. For each vertex v we will also keep track of a source vertex called source(v), which is the vertex closest vertex to v along its shortest path to o. The algorithm is

Dijkstra's Algorithm

1. For each vertex v in G
   1. Label v as Unburned
   2. Set δ(v) = &infin
   3. Set source(v) as undefined
2. Set δ(o) = 0
3. While any vertex is Unburned
   1. Call the Unburned vertex with smallest &delta value u
   2. Label u as Burned
   3. For each neighbor n of u
      1. If δ(u) + w(u,n) < &delta(n)
         1. Set δ(n) = δ(u) + w(u,n)
         2. Set source(n)=u
4. End

If the above doesn't make a lot of sense to you, don't worry; it's written in a way to be digestible to those familiar with computer programming. The indented lines under a given line are done under the condition that line. Once that condition is no longer met you move on in the algorithm. The first part of the algorithm is an initialization of the graph into the setup described earlier; the rest is concerned with searching through the graph to find distances. To illustrate the algorithm we provide an example below.

In the above picture o is marked by a double circle. The Unburned node with the smallest &delta value is orange. It will be burned at the next step in the algorithm. The yellow vertex is the one that is currently burning. Gray vertices have been labeled as Burned by the algorithm. Neighbors if the burning vertex whose &delta is being updated have their edges marked in orange. This happens when δ(u) + w(u,n) < &delta(n). Edges corresponding to sources are marked in blue. Note that the algorithm will occasionally overwrite the source of a vertex with a closer source. Once all the vertices are Burned the algorithm is burned.

Now that we've run the algorithm how do we find the shortest path from o to another vertex? We simply follow the source edges (blue in the example) from the destination until we reach o, and the distance we have travelled corresponds to the label &delta on the destination. We also know that we have actually found the shortest path (it is possible to have more than one path tied for being the shortest) since our fire has always chosen to take the shortest steps possible when moving to a new location.

You might have already noticed that the blue subgraph doesn't contain any loops, and this is what mathematicians call a tree. In fact this is a very special kind of tree called a minimal spanning tree because it grows from the root o to all of its leaves, the other vertices in G, in the shortest way possible. Minimal spanning trees are very useful. For instance, if a cable company needs to wire all the houses in a neighborhood using as little wire as possible, a minimal spanning tree of the neighborhood provides them with the most efficient way to do so.

Activity 1

Varying Weights

We can also think of more complicated shortest path problems. The most basic of which is to have the weight of an edge be random. Suppose you're supposed to meet your friends at the mall in 15 minutes, but it snowed last night. You know of two routes from your house to the mall. Route B takes 17 minutes and is always cleared while the other is a shortcut using roads that are less likely to be cleared.

If road C has been plowed the short cut takes 12 minutes while if it hasn't been plowed it takes 20 minutes. Suppose there is a 75% chance of road C being plowed. In this case you should really think of C as being weighted with the expected value of how long it takes, that is if you were to attempt the drive many times how long would C take on average. In this case road C to takes 0.25(20)+0.75(12)=14 minutes on average. Since the average time for C is faster than B, you should take C to avoid being late.

Activity 2