Problem 3. [10 marks, 1.5 pages] (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( p., d.),

where d, is the length of the current shortest path from the source to v and p, is the

second to last node along that part (right before v). For example, c(a, 1) is one such node.

We treat d, as the key of Node v in the heap, where v = (a, b, c, d, e, f, g, h}.

Source

15

10

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 7.

d(a, 5)

a) [1 mark] The min-heap after a(a,0) is removed is given in Fig. 2. The next node to

be removed from the heap is c(a, 1). Draw the heap after c(a, 1) has been removed

and the tree has been heapified, assuming that ∞ ∞ (note: no need to swap if

both parent and children are ∞o). No intermediate steps are required.

c(0, 1)

) h(-, ∞)

b(a, 7) e(-, ∞) f(-∞)

g(-, ∞)

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

b) [2 marks] Draw the heap(s) after each neighbour of c has been updated and the

tree 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., d must be updated before e. No intermediate steps, i.e., swaps, are

required./nS: vertices whose shortest

paths have been known

1

a(a,0)

2 a(a,0), c(a, 1)

3

4

5

6

7

8

c) [5 marks] 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.

a

b

d) [2 marks] Fill Table 2 with the shortest paths AND the corresponding

distances from a to ALL other vertices in the format a →? →? →v|d, for

instance, a → c | 1.

Shortest Paths

Distances

a → a

C

d

Priority queue of remaining vertices

b(a,7), c(a,1), d(a,5), e(−,∞), ƒ (−,∞), g(−,∞), h(−,∞)

e

f

9

h

Table 1: Complete this table for Part c.

a → c

Table 2: Complete this table for Part d.

0

1