A2 October 2021 Q4

EdexcelCurrent spec8 marksRoute Inspection Shortest Path

Figure 3: network on A, B, C, D, E and F with arcs AB 57, AC 95, AD 150, AE 63, AF 230, BC 72, BE 132, CD 289, CE 160, CF 125, DE 84, EF 191 — Figure 3

[The total weight of the network is 1648]

Direct roads between six cities, A, B, C, D, E and F, are represented in Figure 3. The weight on each arc is the time, in minutes, required to travel along the corresponding road.

Floyd’s algorithm is to be used to find the complete network of shortest times between the six cities.

An initial route matrix is given in the answer book.

Initial route matrix (answer book)

	A	B	C	D	E	F
A	A	B	C	D	E	F
B	A	B	C	D	E	F
C	A	B	C	D	E	F
D	A	B	C	D	E	F
E	A	B	C	D	E	F
F	A	B	C	D	E	F

(a) Set up the initial time matrix. (1)

(b) Perform the first iteration of Floyd’s algorithm. You should show the time and route matrices after this iteration. (2)

The final time matrix after completion of Floyd’s algorithm is shown below.

	A	B	C	D	E	F
A	–	57	95	147	63	220
B	57	–	72	204	120	197
C	95	72	–	242	158	125
D	147	204	242	–	84	275
E	63	120	158	84	–	191
F	220	197	125	275	191	–

A route is needed that minimises the total time taken to traverse each road at least once.

The route must start at B and finish at E.

(c) Use an appropriate algorithm to find the roads that will need to be traversed twice. You should make your method and working clear. (4)

(d) Write down the length of the route. (1)

Mark scheme (a)

Scheme

Marks

Initial time matrix

	A	B	C	D	E	F
A	-	57	95	150	63	230
B	57	-	72	∞	132	∞
C	95	72	-	289	160	125
D	150	∞	289	-	84	∞
E	63	132	160	84	-	191
F	230	∞	125	∞	191	-

1.1b

(1)

Notes

(a) B1: Correct distance table (condone dashes, crosses, etc. for infinity but do not condone a ‘large’ number in these cells or these cells left blank)

Mark scheme (c)

Scheme	Marks	AO
Route must start and finish at B, E therefore need to consider pairings of the other four odd nodes (A, C, D and F)	M1	3.1b
AC + DF = 95 + 275 = 370 AD + CF = 147 + 125 = 272* AF + CD = 220 + 242 = 462	A1 A1	1.1b 1.1b
Repeat arcs: AE, DE and CF	A1	2.2a
	(4)

Notes

(c) M1: Either the correct three pairings of the correct four nodes A, C, D and F or recognises that as the route begins at B and finishes at E that only the nodes A, C, D and F need to be considered

A1: Two rows correct including pairings and totals

A1: All three rows correct including pairings and totals

A1: selecting the shortest pairing, and stating that these arcs (AE, DE and CF) should be repeated. Must be these arcs and not e.g., AED or AD via E, etc.

Scheme	Marks	AO
Length: 1648 + 272 = 1920 (minutes)	B1	2.2a
	(1)
	(8 marks)