9 1 4 9 6 e 9 Figure 2: Undirected weighted graph for minimum spanning trees in Problem 2 and shortest paths in Problem 3. 3 (60 p) Consider again the graph in Figure 2 with the same assumptions. 3a (40p) Run Dijkstra's algorithm by hand on this graph, starting in the vertex a. Use a he ap for the priority queue implementation. Describe for every vertex which neighbours are being considered and how they are dealt with, and show how the heap changes. Also show the tree produced by the algorithm. 3b 20p) If Dijkstra's algorithm is run on an undirected graph, is it true that the spanning tree produced is a minimum spanning tree? Prove this or give a simple counter-example