i have got the mark scheme here for you guys to see, or if it doesnt work its from AQA D1 Jan 08.
its question 4, and i'm having some trouble!
i've done the dijkstra's algorithm and worked everything out correctly. then you have to use chinese postman to find the length of an optimum route. ive identified the odd vertices D, K, A and H, but am confused as how to find the shortest lengths.
i get with the AD, AK and AH edges, the shortest lengths will just be the label i have for them from doing the Dijkstra.
however, i dont get how the mark scheme gets the values for DK, DH and KH.
how are you supposed to identify the shortest routes?do you still use the Dijkstra labels somehow?
any help would be much appreciated, thanks
hi, i did D1 with edexcel but i assume it's the same.
firstly you select the odd order vertices, as you have done, then you work out the distances of all the possibilities of repeating them, so repeating either
AD and KH, AH and KD or AK and HD.
AD and KH would be 27(ABD) +30(KJH) =57
AH and KD would be 20(ACH) + 20(KID)=40
AK and HD would be 46(ABEIK) + 40(DIFJH) =86
you repeat AH and KD because it is shortest and then add that to the weight of the network, so 308 + 40 = 348minutes
hope that helped.