Arrowhead Provincial Park has various trails that people can follow between Ranger Station X and Ranger Station Y. There are trail markers at each intersection which are named after animals that may be seen in the park. The map below shows the trails and the distances between markers. The map is not to scale.
Three hikers walked from Station X to Station Y along different paths:
Path A: Station X \(\rightarrow\) rabbit \(\rightarrow\) deer \(\rightarrow\) Station Y
Path B: Station X \(\rightarrow\) beaver \(\rightarrow\) chipmunk \(\rightarrow\) Station Y
Path C: Station X \(\rightarrow\) rabbit \(\rightarrow\) moose \(\rightarrow\) raccoon \(\rightarrow\) deer \(\rightarrow\) Station Y
Who walked the furthest? Justify your answer.
Find a path that is shorter than any of the three paths the hikers took.
Challenge: What is the shortest path from Station X to Station Y?
One way to solve this problem is to convert all the distances to metres. We know that \(1\) km is equal to \(1000\) m. So, \(2\) km is equal to \(2000\) m and \(\frac{1}{2}\) km is equal to \(1000 \div 2 = 500\) m.
Path A is \(500 + 500 + 1000 = 2000\) m or 2 km long.
Path B is \(750 + 2000 + 300 = 3050\) m long.
Path C is \(500 + 100 + 250 + 100 + 1000 = 1950\) m long.
The hiker that follows Path B walks the furthest.
Answers will vary. Possible answers include:
Station X \(\rightarrow\) rabbit \(\rightarrow\) deer \(\rightarrow\) raccoon \(\rightarrow\) chipmunk \(\rightarrow\) Station Y
The distance of this path is \(500 + 500 + 100 + 300 + 300 = 1700\) m.
Station X \(\rightarrow\) rabbit \(\rightarrow\) moose \(\rightarrow\) raccoon \(\rightarrow\) chipmunk \(\rightarrow\) Station Y
The distance of this path is \(500 + 100 + 250 + 300 + 300 = 1450\) m.
Challenge Solution:
One way to try to find the shortest distance from Station X to Station Y is to look for the paths that have the fewest stops. Both Path A and Path B only have two stops between the starting point and the ending point. There are no possible paths that have only one stop between Station X and Station Y, so Path A and Path B have the fewest stops possible. However, as we already calculated, neither of these two paths can possibly be the shortest path since Path C is shorter. So this strategy for finding the shortest path does not work in general.
Another strategy for searching for the shortest path is called the greedy algorithm. With this strategy, at each intersection we pick the path with the shortest distance leaving that intersection. Path C follows this strategy.
At Station X, we follow the path that is \(500\) m instead of the path that is \(750\) m. At the rabbit intersection, we follow the path that is \(100\) m instead of the path that is \(\frac{1}{2}\) km. At the moose intersection, we follow the path that is \(250\) m instead of the path that is \(400\) m. At the raccoon intersection, we follow the path that is \(100\) m instead of the path that is \(300\) m. At the deer intersection, we follow the path that is \(1\) km instead of the path that leads us back to an intersection we have already visited. We see that this strategy finds a path that is shorter than the other two paths that are listed, but is this the shortest possible path?
In this problem, we can use trial and error to find at least one other path that is shorter than Path C. So the greedy algorithm strategy for finding the shortest path does not work in general.
The next question is, how do we find the shortest path and know that there are no paths that are shorter? We could use trial and error and list all possible paths from Station X to Station Y. Then we choose the shortest path from all possible paths. However, this can get tricky and it is easy to miss one or more paths. There is a strategy that is used in higher mathematics called Dijkstra’s Algorithm. We won’t go through the details of this algorithm here, but the result of following this strategy leads us to the shortest path from Station X to Station Y:
Station X \(\rightarrow\) rabbit \(\rightarrow\) moose \(\rightarrow\) raccoon \(\rightarrow\) chipmunk \(\rightarrow\) Station Y
The distance of this path is \(500 + 100 + 250 + 300 + 300 = 1450\) m.