AS June 2019 Q4

EdexcelAS paperCurrent spec10 marksRoute InspectionShortest Path

4.

Figure 1: network on vertices A to H with arcs AB 10, AC 17, AD 9, BC 5, BE 25, CD 7, CE x + y, CF 7, CG 3, DG 12, EF 16, EH 9, FG 2, FH 13, GH 3x + y
Figure 1

[The total weight of the network is \(135 + 4x + 2y\)]

The weights on the arcs in Figure 1 represent distances. The weights on the arcs CE and GH are given in terms of \(x\) and \(y\), where \(x\) and \(y\) are positive constants and \(7 < x + y < 20\)

There are three paths from A to H that have the same minimum length.

(a) Use Dijkstra’s algorithm to find \(x\) and \(y\). (7)

An inspection route starting at A and finishing at H is found. The route traverses each arc at least once and is of minimum length.

(b) State the arcs that are traversed twice. (1)
(c) State the number of times that vertex C appears in the inspection route. (1)
(d) Determine the length of the inspection route. (1)