Algorithms on graphs

Sample questions

Original practice questions written in the style of the exam.

1. Question 15 marks

   The table lists the arcs of a network and their weights.

   Arc	AB	AC	AD	BC	BE	CD	CE	CF	DF	DG	EF	EG	FG
   Weight	8	5	12	4	7	6	11	10	3	17	12	14	13

   Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order you consider them, stating whether each is accepted or rejected, and give the total weight of the tree.

   Mark scheme

   • M1 Arcs considered in increasing order of weight, starting DF, BC, AC (1)
   • A1 Accept DF, BC, AC, CD, BE (1)
   • A1 Reject AB, CF, CE (they would form cycles) (1)
   • A1 Reject AD and EF, then accept FG (1)
   • A1 Total weight $= 3 + 4 + 5 + 6 + 7 + 13 = 38$ (1)
2. Question 25 marks

   The table lists the arcs of a network and their weights. Use Dijkstra's algorithm to find the shortest route from $A$ to $G$. State the order in which vertices are given permanent labels, the final value at each vertex, and the shortest route and its length.

   Arc	AB	AC	AD	BC	BE	CD	CE	CF	DF	DG	EF	EG	FG
   Weight	8	5	12	4	7	6	11	10	3	17	12	14	13

   Mark scheme

   • M1 Correct use of Dijkstra: working values updated and the smallest made permanent each time (1)
   • A1 Order of labelling: A, C, B, D, F, E, G (1)
   • A1 Final values: A 0, C 5, B 8, D 11, F 14, E 15, G 27 (1)
   • A1 Shortest route $A\to C\to$ (1)