Problem 3. (Dijkstra’s algorithm + min-heap) Given a graph as in Fig. 1, we are interested in finding the shortest paths from the source a to all other vertices using the Dijkstra’s algorithm and a min-heap as a priority queue. Note that a min-heap is the same as a max-heap, except that the key stored at a parent node is required to be smaller than or equal to the keys stored at its two child nodes. In the context of the Dijkstra’s algorithm, a node in the min-heap tree has the format v(pv,dv), where dv is the length of the current shortest path from the source to v and pv is the second to last node along that part (right before v). For example, b(a,4) is one such node. We treat dv as the key of Node v in the heap, where v ∈ {a,b, c,d, e, f , g,h}.

Figure 1: An input graph for the Dijkstra’s algorithm. Edge weights are given as integers next to the edges. For example, the weight of the edge (a,b) is 4.

a) The min-heap after a(a,0) is removed is given in Fig. 2. The next node to be removed from the heap is b(a,4). Draw the heap after b(a,4) has been removed and the heap has been heapified (fixed), assuming that ∞ ≥ ∞. No intermediate steps are required.

Figure 2: The min-heap (priority queue) after a(a,0) has been removed.

b) Draw the heap(s) after the neighbours of b have been updated and the heap has been heapified (see the pseudocode in the lecture Slide 30, Week 9). If there are multiple updates then draw multiple heaps, each of which is obtained after one update. Note that neighbours are updated in the alphabetical order, e.g., b must be updated before c. No intermediate steps are required. Follow the discussion on Ed Forum for how to update a node in a heap.

c) Complete Table 1 with correct answers. You are required to follow strictly the steps in the Dijkstra’s algorithm taught in the lecture of Week 9.

d) Fill Table 2 with the shortest paths AND the corresponding distances from a to ALL other vertices in the format a →? →? → v | dv, for instance, a → b | 4.