Floyd's Algorithm Application

3 The weights on the network represent distances.
\includegraphics[max width=\textwidth, alt={}, center]{88acde67-e22b-478a-9145-48abe931beff-3_401_702_315_683}

1. 1. Apply Floyd's algorithm to the network to find the complete network of shortest distances, showing that the final matrices are as follows. \begin{center} \begin{tabular}{ | c | c | c | c | c | } \cline { 2 - 5 } \multicolumn{1}{c|}{} & \(\mathbf { 1 }\) & \(\mathbf { 2 }\) & \(\mathbf { 3 }\) & \(\mathbf { 4 }\)
      \hline \(\mathbf { 1 }\) & 22 & 14 & 11 & 23
      \hline \(\mathbf { 2 }\) & 14 & 28 & 15 & 27
      \hline \(\mathbf { 3 }\) & 11 & 15 & 22 & 12
      \hline

4 The diagram shows routes connecting five cities. Lengths are in km .
\includegraphics[max width=\textwidth, alt={}, center]{ae8dc840-0c61-4ba5-b082-1f5f3e6c2cef-4_442_995_319_534}

1. Produce the initial matrices for an application of Floyd's algorithm to find the complete network of shortest distances between the five cities. The following are the distance and route matrices after the third iteration of Floyd's algorithm. \begin{center} \begin{tabular}{ | c | c | c | c | c | c | } \cline { 2 - 6 } \multicolumn{1}{c|}{} & \(\mathbf { 1 }\) & \(\mathbf { 2 }\) & \(\mathbf { 3 }\) & \(\mathbf { 4 }\) & \(\mathbf { 5 }\)
   \hline \(\mathbf { 1 }\) & 44 & 22 & 42 & 15 & 15
   \hline \(\mathbf { 2 }\) & 22 & 44 & 20 & 5 & 23
   \hline \(\mathbf { 3 }\) & 42 & 20 & 40 & 25 & 43
   \hline \(\mathbf { 4 }\) & 15 & 5 & 25 & 10 & 16
   \hline

2 The network is a representation of a show garden. The weights on the arcs give the times in minutes to walk between the six features represented by the vertices, where paths exist.
\includegraphics[max width=\textwidth, alt={}, center]{c3a528e4-b5fe-4bff-a77e-e3199bb225a1-3_483_985_342_539}

1. Why might it be that the time taken to walk from vertex \(\mathbf { 2 }\) to vertex \(\mathbf { 3 }\) via vertex \(\mathbf { 4 }\) is less than the time taken by the direct route, i.e. the route from \(\mathbf { 2 }\) to \(\mathbf { 3 }\) which does not pass through any other vertices? The matrices shown below are the results of the first iteration of Floyd's algorithm when applied to the network. \begin{center} \begin{tabular}{ | c | c | c | c | c | c | c | } \cline { 2 - 7 } \multicolumn{1}{c|}{} & \(\mathbf { 1 }\) & \(\mathbf { 2 }\) & \(\mathbf { 3 }\) & \(\mathbf { 4 }\) & \(\mathbf { 5 }\) & \(\mathbf { 6 }\)
   \hline \(\mathbf { 1 }\) & \(\infty\) & 15 & \(\infty\) & \(\infty\) & 7 & 8
   \hline \(\mathbf { 2 }\) & 15 & 30 & 6 & 2 & 6 & 23
   \hline

\(\mathbf { 4 }\) & \(\infty\) & 2 & 3 & \(\infty\) & 10 & 17
\hline

3 Floyd's algorithm is applied to the incomplete network on 4 nodes drawn below. The weights on the arcs represent journey times.
\includegraphics[max width=\textwidth, alt={}, center]{4b5bc097-1052-4e44-8623-a84ceaab0289-4_400_558_347_751} The final matrices are shown below. \begin{table}[h] \begin{center} \captionsetup{labelformat=empty} \caption{final time matrix} \begin{tabular}{ | l | r | r | r | r | } \cline { 2 - 5 } \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{\(\mathbf { 1 }\)} & \(\mathbf { 2 }\) & \(\mathbf { 3 }\) & \multicolumn{1}{c|}{\(\mathbf { 4 }\)}
\hline \(\mathbf { 1 }\) & 6 & 5 & 3 & 10
\hline \(\mathbf { 2 }\) & 5 & 4 & 2 & 5
\hline \(\mathbf { 3 }\) & 3 & 2 & 4 & 7
\hline

\(\mathbf { 5 }\) & 4 & - & - & 2
\hline \end{tabular} \end{center} (iii) Draw the complete 5-node network of shortest times. (You are not required to use an algorithm to find the shortest times.)
(iv) Write down the final time matrix and the final route matrix for the complete 5 -node network. (You do not need to apply Floyd's algorithm.)
(v) (A) Apply the nearest neighbour algorithm to the complete 5-node network of shortest times, starting at node 1. Give the time for the cycle you produce.
(B) Starting at node 3, a possible cycle in the complete 5-node network of shortest times is \(\mathbf { 3 2 1 5 4 3 . }\) Give the actual cycle to which this corresponds in the incomplete 5-node network of journey times.
(vi) By deleting node 5 and its arcs from the complete 5 -node network of shortest times, and then using Kruskal's algorithm, produce a lower bound for the solution to the associated practical travelling salesperson problem. Show clearly your use of Kruskal's algorithm.
(vii) In the incomplete 5-node network of journey times, find a quickest route starting at node \(\mathbf { 5 }\) and using each of the 7 arcs at least once. Give the time of your route. 4 Helen has a meeting to go to in London. She has to travel from her home in G on the south coast to KC in London. She can drive from G to the west to A to catch a train, or she can drive to the east to W to catch a train on a different line. From both A and W she can travel to mainline terminuses V or LB in London. She will then travel by tube either from V to KC , or from LB to KC . The times for the various steps of her journey are shown in the tables. Both train services and tube services are subject to occasional delays, and these are modelled in the tables. Helen wants to choose the route which will give the shortest expected journey time.
(i) Draw a decision tree to model Helen's decisions and the possible outcomes.
(ii) Calculate Helen's shortest expected journey time and give the route which corresponds to that shortest expected journey time. As she gets into her car, Helen hears a travel bulletin on the radio warning of a broken escalator at V. This means that routes through V will take Helen 10 minutes longer.
(iii) Find the value of the radio information, explaining your calculation.
(iv) Why might the shortest expected journey time not be the best criterion for choosing a route for Helen?

\(\mathbf { 4 }\) & 11 & 11 & 7 & 14 & 14
\hline

5. \begin{figure}[h] \end{figure} [The total weight of the network is 106.7]
Figure 3 models a network of cycle tracks that have to be inspected. The number on each arc represents the length, in km , of the corresponding track. Angela needs to travel along each cycle track at least once and wishes to minimise the length of her inspection route. She must start and finish at A.

1. Use an appropriate algorithm to find the tracks that will need to be traversed twice. You should make your method and working clear.
2. Find a route of minimum length, starting and finishing at A . State the length of your route. A new cycle track, AC, is under construction. It will be 15 km long. Angela will have to include this new track in her inspection route.
3. State the effect this new track will have on the total length of her route. Justify your answer.

6. \begin{figure}[h] \end{figure} Figure 4 represents a network of roads. The number on each arc represents the time taken, in minutes, to drive along the corresponding road. Stieg wishes to minimise the time spent driving from his home at A , to his office at H . The amount of traffic on two of the roads leading into H varies each day, and so the length of time taken to drive along these roads is expressed in terms of \(x\), where \(x > 7\)

1. Use Dijkstra's algorithm to find the possible routes that minimise the driving time from A to H . State the length of each route, leaving your answer in terms of \(x\) where necessary.
   (7) On a particular day, the quickest route from A to H via G is 2 minutes quicker than the quickest route from A to H via E .
2. Calculate the value of \(x\). You must make your method and working clear.