5.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 3}
\includegraphics[alt={},max width=\textwidth]{e64b50bc-13a3-4051-b8c1-d4e7ea49e3a5-5_590_1360_1265_331}
\end{figure}
Figure 3 shows a network of paths. The number on each arc gives the distance, in metres, of that path.
- Use Dijkstra's algorithm to find the shortest distance from \(A\) to \(H\).
(5) - Solve the route inspection problem for the network shown in Figure 3. You should make your method and working clear. State a shortest route, starting at \(A\), and find its length.
[0pt]
[The total weight of the network is 1241]
(6)
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 4}
\includegraphics[alt={},max width=\textwidth]{e64b50bc-13a3-4051-b8c1-d4e7ea49e3a5-6_634_1486_301_312}
\end{figure}
Figure 4 shows a capacitated directed network. The number on each arc is its capacity.
(a) State the maximum flow along - SADT,
- SCET,
- \(S B F T\).
(b) Show these maximum flows on Diagram 1 in the answer book.
Take your answer to part (b) as the initial flow pattern.
(c) (i) Use the labelling procedure to find a maximum flow from \(S\) to \(T\). Your working should be shown on Diagram 2 in the answer book. List each flow-augmenting route you use, together with its flow. - Draw your final flow pattern on Diagram 3 in the answer book.
- Prove that your flow is maximal.
(d) Give an example of a practical situation that could have been modelled by the original network.