In Gridville, the POTW Delivery Company needs to deliver nine packages to nine different locations. In the diagram below, the location where they start is labelled with an \(S\). The nine other circles indicate where the nine delivery locations are. These locations are joined by roads, which are shown as lines. The number beside each line indicates the average time, in minutes, it will take to travel along that road.
If the POTW Delivery Company does not want to visit any location more than once, but can finish at any location, what is the shortest amount of time that they will take to deliver the nine packages?
There are only five possible paths that start at \(S\) and visit each of the locations exactly once:
To justify this, notice that we have two choices for where to travel
from \(S\): down or right.
If we travel right first, then the rest of our path is determined. If we move down before reaching the rightmost location in the top row, then we would need to backtrack to reach all of the bottom locations. This would mean revisiting at least one location on the way. Therefore, we must travel right until we reach the rightmost location in the top row, and then must follow path 1) for the remainder.
If we travel down first, then we must travel right next, but then there we again have two options: up or right.
If we travel right, then the rest of our path is determined. We cannot move up next, as then we cannot reach all of the top locations without backtracking, and so we must move right. From here we would have to follow path 2) for the remainder.
If we travel up, then we must travel right next. From here we once again we have two choices: down or right.
If we travel right, then the rest of our path is determined. We must follow path 3).
If we travel down, then we must travel right next, and then we once more have two choices: up or right.
If we travel right then the rest of our path is determined. We must follow path 4).
If we travel up then the rest of our path is determined. We must follow path 5).
These five possible paths have the total times of:
\(3 + 3 + 4 + 6 + 4 + 5 + 2 + 3 + 1 = 31\)
\(2 + 1 + 3 + 2 + 5 + 4 + 6 + 4 + 3 = 30\)
\(2 + 1 + 5 + 3 + 4 + 6 + 4 + 5 + 2 = 32\)
\(2 + 1 + 5 + 3 + 1 + 2 + 5 + 4 + 6 = 29\)
\(2 + 1 + 5 + 3 + 1 + 2 + 8 + 6 + 4 = 32\)
(where the sum is shown starting at \(S\) and moving through the path).
Therefore, the shortest amount of time to deliver the nine packages is \(29\) minutes.