9.03 Shortest path problems

A common problem posed in networks is to find the path of lowest weight between two vertices. For example, finding the best (fastest, shortest, cheapest) route between two destinations.

Let’s take a look at this network of towns.

The weights represent travel time in minutes, and we want to get from A to B via the optimal (fastest) path. Here are three paths we could take:

• The red path AB will take 9 minutes.

• The blue path ACEB will take 2+3+4=9 minutes.

• The green path ADB will take 4+4=8 minutes.

This last path is close to the answer, but we can get from A to D even faster if we take a shortcut through C.

This path does not look like the fastest but it takes 2+1+4=7 minutes, and is the quickest way to get from A to B.

We can perform the same sort of analysis on directed graphs as well, just be careful to follow the direction on the arrows when forming paths.

Here is a directed graph. This time, the streets are all one-way.

Let’s try a few paths out:

• The blue path AFG takes 10+11=21 minutes.

• The green path ADG takes 4+12=16 minutes.

• The purple path ABCEG takes6+1+5+5=17 minutes.

We can now check more paths, thinking about taking detours on paths we already know about. Starting from the path ADG, the best one we have found so far, we can improve the trip from D to G by going through E.

Going along the path ADEG only takes \\ 4+6+5=15 minutes, and this is the fastest route.

Using trial and error is an appropriate method when solving shortest path problems. However, we need to be careful as it can sometimes be difficult to ensure all paths are checked. Systematically recording the paths and eliminating paths that contain extended detours from the shortest path found so far can help avoid missing possible solutions and is effective for finding the shortest path on networks that are relatively small or not overly complex.

Examples

Example 1

A rock band is planning a tour across several cities. The following table represents the routes and distance between the cities at which they will be performing.

Starting City	Ending City	Distance
A	C	9
A	F	6
B	E	11
B	F	5
C	D	3
C	F	7
E	D	5
E	F	8

a

Which of the following graphs does the table represent?

A

B

C

D

Worked Solution

Create a strategy

Compare the routes and distances in the table with each of the graphs.

Apply the idea

Looking at the table, starting at A and ending at C, there is a distance of 9. So the edge AC must have a weight of 9. That means that option A cannot be the answer.

In the last row of the table, starting at E and ending at F, there is a distance of 8. The only remaining graph that has the edge EF with weight 8, is option C.

So the correct answer is option C.

Watch question walkthrough

b

Using either the correct graph or table given, find the shortest route for the rock band to cross starting at city A and passing by each city only once.

Worked Solution

Create a strategy

At each vertex, choose the edge that has the lowest weight until all vertices have been visited.

Apply the idea

From A we move to F since 6 \lt 9.

From F we move to B since 5\lt 7 \lt 8.

From B we move to E since it is the only remaining option.

From E we move to D since it is the only remaining option.

From D we move to C since it is the only remaining option.

So the shortest route for the rock band to cross starting at city A and passing by each city only once is: \text{Shortest route} = A,\,F,\,B,\,E,\,D,\,C

Reflect and check

There are other routes with the same total weight. The weight of the above route is 6+5+11+5+3=30.

Another route that has the same total weight, and so would also be the shortest route is: A,\,C,\,D,\,E,\,F,\,B

Watch question walkthrough

There are many applications of networks where the most important question to ask is:

What is the lowest weight path from one vertex to another?

Dijkstra's algorithm (pronounced DIKE-stra) published not long ago in 1959 was devised by the computer scientist Edsger Dijkstra. He published the algorithm three years after he conceived it, to illustrate the power of computing and coding. It is guaranteed to give the right answer by looping through a sequence of simple steps. This means it is very suitable to be done by a computer program - the complexity of the network is irrelevant, since a computer can do this kind of algorithm extremely quickly.

Every time we ask for directions from an online service, this is exactly how it will figure it out for us. We will apply the procedure to find the shortest path between two vertices in a network.

This network represents the travel times for an ambulance to get between the seven townships it services:

The ambulance is stationed at Eastfarthing when it receives a call for help from Arda. This is an emergency, and the ambulance needs to get there as fast as possible - what route should it take?

First of all, remove the information we won’t be using, replace each of the towns with the first letter, move the vertices around a bit, and straighten out the edges:

Take a moment to see how the two networks match up. Sometimes there will be equivalent representations of the same network.

There are a number of methods used to work through Dijksta's algorithm. This one uses a box at each vertex. These boxes will record useful numbers as we perform the algorithm in three sections:

• top left is for the order in which the vertex is selected (starting at 1 and working upwards)

• top right is for the distance between each vertex and the start vertex

• bottom is for temporary distance labels that we will add to as the procedure continues.

1. Start by drawing a special box at each vertex:

   

2. Select the start vertex, or working vertex, in this case E

3. Place a '1' in the order(top left) section. There is no distance from Eto itself, so place a '0' in the distance(top right) section.

   

4. Follow each edge out of this working vertex, and write the weight of the edge in the temporary section of the vertex at the other end:

   

   We are now finished with this vertex and will move on to the next one.

5. Find the smallest temporary label on the unused vertices (which is G), mark its order as '2' (since it’s second) and transfer the temporary label (which is 6) to be its new distance:

   

   This is now the working vertex. Repeat the above Steps 3 \text{-}5 to record temporary labels(bottom sections), but this time:

   • add the distance of the working vertex (which in this case is 6) to the weight of each edge, and

   • only write the number as a new temporary label if it’s less than the temporary labels we've already written (which only happens at B):

   

   Note: that we didn't write 18 at F or 22 at C, since there was already a smaller temporary label.

   Loop back through the algorithm and choose a new working vertex (the one with the smallest temporary label, which is F) and update its order and distance sections:

   

   Do the same as before, adding the distance of the weight of each edge and adjusting the temporary labels:

   

   This time write 20, since it is less than the existing temporary label.

   Once again pick a new working vertex, updating the order and distance:

   

   Update the temporary labels for edges coming out of the working vertex:

   

   Pick a new working vertex, updating the order and distance:

   

   Update the temporary label at vertex A:

   

   Pick the new working vertex:

   

   Write the last temporary label:

   

6. The last vertex that hasn’t been picked (which is A) is not going to be a working vertex, but we update the order and distance fields in the same way: since it is less than the existing temporary label.

   Once again pick a new working vertex, updating the order and distance:

   

   The procedure is now complete. We now don’t need any numbers except the final distances.

7. Transfer the final distances onto the vertices themselves (or highlight them):

   

   Highlight the shortest paths starting at E, by picking the edges that make the shortest paths to each vertex, making sure the weights match up with the distances calculated.

   Now we know how the ambulance should travel and how long it will take: Through Cambray, Belconnen then to Arda, and it will take 22 minutes.

   In fact, we know the fastest route and travel times from the station to Dolby and Belconnen as well: both through Cambray, 17 minutes to Dolby and 18 minutes to Belconnen.

This is a spanning tree, but it may not be the minimal spanning tree for the network. Changing the start vertex may also change the tree we produce.

This procedure, once completed, tells us the weight of the lowest weight path from the start vertex to each of the vertices in the network.

Dijkstra's algorithm

1. Write the order '1' and distance '0' at the start vertex. This vertex is now the working vertex.

2. Add the distance of the working vertex to the weight of each edge coming out it, writing it as a temporary label at the other end. Only write the temporary label if it is smaller than the temporary labels already there.

3. Find the smallest temporary label written at a vertex that hasn’t been a working vertex yet. This vertex is the new working vertex.

4. Add one to the previous order and write it at the new working vertex. Transfer the smallest temporary label to be its distance.

5. If this would be the last working vertex, transfer the final distances to the vertices and highlight the shortest paths. Otherwise,repeat this procedure from step 2.

Examples

Example 2

In the following graph, we want to find the paths of lowest weight between the vertex A and each of the other vertices. To do this, we will use Dijkstra's algorithm.

a

Using the algorithm, write the order (upper box) and label list (lower box) for each vertex.

Worked Solution

Create a strategy

Start at vertex A and use Dijkstra's algorithm.

1. Write the order '1' and distance '0' at vertex A.

2. Add the distance of the working vertex to the weight of each edge coming out it, writing it as a temporary label at the other end. Only write the temporary label if it is smaller than the temporary labels already there.

3. Find the smallest temporary label written at the new working vertex.

4. Add one to the previous order and write it at the new working vertex. Transfer the smallest temporary label to be its distance.

5. If this would be the last working vertex, transfer the final distances to the vertices and highlight the shortest paths. Otherwise,repeat this procedure from step 2.

Apply the idea

Starting with vertex A, use Dijkstra's Algorithm to the graph.

In vertex A, write an order of 1 and start updating the label lists of each vertex where appropriate at each step. After each step, choose the next working vertex and assign it an order.

For each unused vertex adjacent to the working vertex, find the sum of the connecting edge's weight and the working vertex's lowest label. If the result is less than all of the unused vertex's labels, add it to the list.

Once each vertex is updated in this way, select the unused vertex with the lowest label as the new working vertex and give it an order.

Write the order on the upper box and the label list on the lower box for each vertex.

Vertex	Order	Label list
A	1	0
B	3	5, 4
C	4	17, 10
D	6	22, 15
E	5	12, 11
F	2	3

Watch question walkthrough

b

For each vertex, write the least weight between itself and vertex A.

Worked Solution

Create a strategy

Look at the label list for each vertex and choose the smallest value.

Apply the idea

In part (a) we have found the label list for each vertex. So we have:

Vertex	Order	Label list	Least weight
A	1	0	0
B	3	5, 4	4
C	4	17, 10	10
D	6	22, 15	15
E	5	12, 11	11
F	2	3	3

Watch question walkthrough