Floyd's algorithm application

3 Floyd's algorithm is applied to the following network: \includegraphics[max width=\textwidth, alt={}, center]{483a681e-011a-464f-b7cb-007d894d1516-3_398_394_331_833} At the end of the third iteration of the algorithm the distance and route matrices are as follows:

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.

      \cline { 2 - 5 } \multicolumn{1}{c|}{}	\(\mathbf { 1 }\)	\(\mathbf { 2 }\)	\(\mathbf { 3 }\)	\(\mathbf { 4 }\)
      \(\mathbf { 1 }\)	22	14	11	23
      \(\mathbf { 2 }\)	14	28	15	27
      \(\mathbf { 3 }\)	11	15	22	12
      \(\mathbf { 4 }\)	23	27	12	24

Draw the complete network of shortest distances.
(ii) Starting at vertex 1, apply the nearest neighbour algorithm to the complete network of shortest distances to find a Hamilton cycle. Give the length of your cycle and interpret it in the original network.
(iii) By temporarily deleting vertex \(\mathbf { 1 }\) and its connecting arcs from the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson's Problem in that network. Say what this implies in the original network.
(b) Solve the route inspection problem in the original network, and say how you can be sure that your solution is optimal. 4 A factory's output includes three products. To manufacture a tonne of product \(\mathrm { A } , 3\) tonnes of water are needed. Product B needs 2 tonnes of water per tonne produced, and product C needs 5 tonnes of water per tonne produced. Product A uses 5 hours of labour per tonne produced, product B uses 6 hours and product C uses 2 hours. There are 60 tonnes of water and 50 hours of labour available for tomorrow's production.
(i) Formulate a linear programming problem to maximise production within the given constraints.
(ii) Use the simplex algorithm to solve your LP, pivoting first on your column relating to product C.
(iii) An extra constraint is imposed by a contract to supply at least 8 tonnes of A . Use either two stage simplex or the big M method to solve this revised problem.

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.

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	\(\mathbf { 1 }\)	\(\mathbf { 2 }\)	\(\mathbf { 3 }\)	\(\mathbf { 4 }\)	\(\mathbf { 5 }\)
   \(\mathbf { 1 }\)	44	22	42	15	15
   \(\mathbf { 2 }\)	22	44	20	5	23
   \(\mathbf { 3 }\)	42	20	40	25	43
   \(\mathbf { 4 }\)	15	5	25	10	16
   \(\mathbf { 5 }\)	15	23	43	16	30

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.

   \cline { 2 - 7 } \multicolumn{1}{c|}{}	\(\mathbf { 1 }\)	\(\mathbf { 2 }\)	\(\mathbf { 3 }\)	\(\mathbf { 4 }\)	\(\mathbf { 5 }\)	\(\mathbf { 6 }\)
   \(\mathbf { 1 }\)	\(\infty\)	15	\(\infty\)	\(\infty\)	7	8
   \(\mathbf { 2 }\)	15	30	6	2	6	23

\(\mathbf { 3 }\) & \(\infty\) & 6 & \(\infty\) & 3 & \(\infty\) & \(\infty\) \hline

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

\(\mathbf { 5 }\) & 7 & 6 & \(\infty\) & 10 & 14 & 8
\hline

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

6. \section*{Question 6 continued} (b) \(\_\_\_\_\) (c) \section*{Question 6 continued}

3. \begin{figure}[h] \end{figure} Direct roads between five villages, A, B, C, D and E, are shown in Figure 2. The weight on each arc is the time, in minutes, it takes to travel along the corresponding road. The road from D to C is one-way as indicated by the arrow on the corresponding arc. Floyd's algorithm is to be used to find the complete network of shortest times between the five villages.

1. Set up initial time and route matrices. The matrices after two iterations of Floyd's algorithm are shown below. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Time matrix}

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	A	B	C	D	E
   A	-	8	4	7	18
   B	8	-	3	15	10
   C	4	3	-	11	6
   D	7	15	1	-	1
   E	18	10	6	1	-

   \end{table} \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Route matrix}

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	A	B	C	D	E
   A	A	B	C	D	B
   B	A	B	C	A	E
   C	A	B	C	A	E
   D	A	A	C	D	E
   E	B	B	C	D	E

   \end{table}
2. Perform the next two iterations of Floyd's algorithm that follow from the tables above. You should show the time and route matrices after each iteration. The final time matrix after completion of Floyd's algorithm is shown below. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Final time matrix}

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	A	B	C	D	E
   A	-	7	4	7	8
   B	7	-	3	10	9
   C	4	3	-	7	6
   D	5	4	1	-	1
   E	6	5	2	1	-

   \end{table}
3. 1. Use the nearest neighbour algorithm, starting at A , to find a Hamiltonian cycle in the complete network of shortest times.
   2. Find the time taken for this cycle.
   3. Interpret the cycle in terms of the actual villages visited.

3. The initial distance matrix (Table 1) shows the lengths, in metres, of the corridors connecting six classrooms, A, B, C, D, E and F, in a school. For safety reasons, some of the corridors are one-way only. \begin{table}[h] \end{table}

1. By adding the arcs from vertex A, along with their weights, complete the drawing of this network on Diagram 1 in the answer book. Floyd's algorithm is to be used to find the complete network of shortest distances between the six classrooms. The distance matrix after two iterations of Floyd's algorithm is shown in Table 2. \begin{table}[h]

   	A	B	C	D	E	F
   A	-	12	29	20	29	11
   B	12	-	17	8	41	23
   C	29	17	-	4	12	40
   D	24	36	4	-	53	13
   E	\(\infty\)	\(\infty\)	12	18	-	12
   F	11	23	40	13	12	-

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table}
2. Perform the next two iterations of Floyd's algorithm that follow from Table 2. You should show the distance matrix after each iteration. The final distance matrix after completion of Floyd's algorithm is shown in Table 3.

   	A	B	C	D	E	F
   A	-	12	24	20	23	11
   B	12	-	12	8	24	21
   C	28	17	-	4	12	17
   D	24	21	4	-	16	13
   E	23	29	12	16	-	12
   F	11	23	17	13	12	-

   \section*{Table 3} Yinka must visit each classroom. He will start and finish at E and wishes to minimise the total distance travelled.
3. 1. Use the nearest neighbour algorithm, starting at E, to find two Hamiltonian cycles in the completed network of shortest distances.
   2. Find the length of each of the two cycles.
   3. State, with a reason, which of the two cycles provides the better upper bound for the length of Yinka's route.

2 Answer this question on the insert provided. Fig. 2 shows a network in which the weights on the arcs represent distances. \begin{figure}[h] \end{figure}

1. Apply Floyd's algorithm on the insert provided to find the complete network of shortest distances.
2. Show how to use your final matrices to find the shortest route from vertex \(\mathbf { 1 }\) to vertex 3, together with the length of that route.
3. Use the nearest neighbour algorithm, starting at vertex 1, to find a Hamilton cycle in the complete network of shortest distances. Give the corresponding cycle in the original network, together with its length.

4 An algorithm is represented by the flow diagram below. \includegraphics[max width=\textwidth, alt={}, center]{10ca0bf1-beaa-4460-8f28-08f0e4e44d5c-04_1871_1719_293_173} The algorithm is applied with \(n = 4\) and the table of inputs \(\mathrm { d } ( i , j )\) : $$j = 1 \quad j = 2 \quad j = 3 \quad j = 4$$ $$\begin{aligned} & i = 1 \\ & i = 2 \\ & i = 3 \\ & i = 4 \end{aligned}$$ An incomplete trace through the algorithm is shown below. The next box to be used is the box 'Let \(i = t\) '.

1. Complete the trace in the Printed Answer Booklet. The table of inputs represents a weighted matrix for a network, where the weights represent distances.
2. 1. State how the output of the algorithm relates to the network represented by the matrix.
   2. How can the list A be used in the solution of the travelling salesperson problem on the network represented by the matrix?
   3. Write down a limitation on the distances \(\mathrm { d } ( i , j )\) for this algorithm.
3. Explain why the algorithm is finite for any table of inputs. Suppose that, for a problem with \(n\) vertices, the run-time for the algorithm is given by \(\alpha D + \beta T\), where \(\alpha\) and \(\beta\) are constants, \(D\) is the number of times that a value of \(\mathrm { d } ( i , j )\) is looked up and \(T\) is the number of times that \(t\) is updated.
4. Show how this means that the algorithm has \(\mathrm { O } \left( n ^ { 2 } \right)\) complexity. A computer takes 3 seconds to run the algorithm for a problem with \(n = 35\).
5. Use the complexity to calculate an approximate run-time for a problem with \(n = 100\). The run-time using a second algorithm has \(\mathrm { O } ( n ! )\) complexity.
   A computer takes 2.8 seconds to run the second algorithm for a problem with \(n = 35\).
6. Without performing any further calculations, give a reason why the first algorithm is likely to be more efficient than the second for a problem with \(n = 100\).