12.08 Systematic approach for shortest route

Shortest path algorithm

In the previous section, we found the shortest path by trial and error, however, it can often be difficult to find the shortest path this way, even for small networks.

The worked example below, demonstrates a method to find the shortest path between two vertices in a systematic way.

 

Worked example

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

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

First of all, we are going to get rid of the information we won’t be using. We will replace each of the towns with their first letter, move the vertices around a bit, remove the mountains, lakes, and forest, and straighten out the edges:

Take a moment to see how the two networks match up - they are two equivalent representations of the same network.

To find the shortest path from $A$A to $G$G follow the steps below:

Step 1:

• Start at $A$A and write $0$0 in the vertex to indicate this is the start.
• Calculate the distance from $A$A to $B$B is $0+4=4$0+4=4 and write $4$4 on edge $AB$AB (near the vertex $B$B).
• Calculate the distance from $A$A to $D$D is $0+6=6$0+6=6, and write $6$6 on edge $AD$AD (near the vertex$D$D).
• There is only one edge leading into $D$D from $A$A therefore we can write $6$6 in the vertex for $D$D. A quick check tells us path $ADCB$ADCB is more than $4$4, therefore we can write $4$4 in the vertex for $B$B.
• Important! Only write a number in the vertex when you have a number written on every edge leading into the vertex. If it's not possible to write in the vertex circle then you can put a box around the lowest number instead.

Step 2:

• From $B$B add $4$4 and $4$4 to calculate path $ABC$ABC is $8$8, and write $8$8 on edge $BC$BC near to vertex $C$C.
• From $D$D add $6$6 and $3$3 to make $9$9 and write $9$9 on edge $DC$DC near to vertex $C$C.
• Now vertex $C$C has all edges complete with a number. We see all edges into $C$C are complete and that $8$8 is the lowest number therefore $8$8 is written in vertex $C$C. This means the shortest path from $A$A to $C$C is length $8$8.

Step 3

• From $B$B add $4$4 and $12$12 to make $16$16; a quick check confirms that this is clearly the shortest path so we can write $16$16 in vertex $F$F.
• From $B$B add $4$4 and $22$22 to make $26$26, and write $26$26 on edge $BG$BG near vertex $G$G.
• From $C$C add $8$8 and $16$16 to make $24$24, and write $24$24 on edge $CG$CG near vertex $G$G.
• From $C$C add $8$8 and $14$14 to make $22$22, and write $22$22 on edge $CE$CE near vertex $E$E.

Step 4

• From $F$F add $16$16 and $8$8 to make $24$24 and write $24$24 on edge $FE$FE near vertex $E$E.
• We can see that $22$22 is smaller than $24$24 so $22$22 is written in vertex $E$E.

Step 5

• From $F$F add $16$16 and $12$12 to make $28$28 and write $28$28 on edge $FG$FG near vertex $G$G.
• From $E$E add $22$22 and $6$6 to make $28$28 and write $28$28 on edge $EG$EG near vertex $G$G.
• We can now see that all four edges leading into $G$G have a number written on them. The smallest number going into vertex $G$G is $24$24 so we write $24$24 in vertex $G$G.

Step 6

• Follow the numbers written in the vertices backwards through the network to find the shortest path.
• Start at $G$G. The vertex contains the number $24$24 so we follow and highlight the path labelled $24$24 (edge $GC$GC) to $C$C.
• From $C$C, which contains the number $8$8, we follow and highlight the path labelled $8$8 (edge $CB$CB) to $B$B.
• From $B$B, which contains the number $4$4, we follow and highlight the path labelled $4$4 (edge $BA$BA) to $A$A.

Solution: The shortest path for the ambulance is $A$A, $B$B, $C$C, $G$G and the time taken is $24$24 minutes.

 

Practice questions

Question 1

Question 2