3 [Figure 1, printed on the insert, is provided for use in this question.]
The diagram shows roads connecting some places of interest in Berlin. The numbers represent the times taken, in minutes, to walk along the roads.
\includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-4_1427_1404_502_319} The total of all walking times is 167 minutes.

1. Mia is staying at \(D\) and is to visit \(H\).
   1. Use Dijkstra's algorithm on Figure 1 to find the minimum time to walk from \(D\) to \(H\).
   2. Write down the corresponding route.
2. Each day, Leon has to deliver leaflets along all of the roads. He must start and finish at \(A\).
   1. Use your answer to part (a) to write down the shortest walking time from \(D\) to \(A\).
   2. Find the walking time of an optimum Chinese Postman route for Leon. (6 marks)