Data Structures, Algorithms, & Applications in C++
Chapter 17, Exercise 29

We will use d and p as abbreviations for distanceFromSource and predecessor, respectively.

(a)

The initial d and p arrays are given below. n denotes null.

  i    1   2   3   4   5   6   7   8   9   10
d[i]   0   2   n  20   n   n   n   n   n    n   
p[i]   0   1  -1   1  -1  -1  -1  -1  -1   -1

The list newReachableVertices is [2, 4] initially.

(b)

The arrays after the first iteration are given below.

  i    1   2   3   4   5   6   7   8   9   10
d[i]   0   2   n  20   2   n   n   n   n    n   
p[i]   0   1  -1   1   3  -1  -1  -1  -1   -1

The list newReachableVertices becomes [4, 5].
The arrays after the second iteration are

  i    1   2   3   4   5   6   7   8   9   10
d[i]   0   2  10  20   2   n   n   6   n    n   
p[i]   0   1   5   1   3  -1  -1   5  -1   -1

The list newReachableVertices becomes [3, 4, 8].
The arrays after the third iteration are

  i    1   2   3   4   5   6   7   8   9   10
d[i]   0   2  10  20   3   8   n   6   n    8   
p[i]   0   1   5   1   2   8  -1   5  -1    8

The list newReachableVertices becomes [3, 4, 6, 10].
For the fourth iteration assume that vertex 6 is selected in Step 3. The arrays after the fourth iteration are

  i    1   2   3   4   5   6   7   8   9   10
d[i]   0   2   9  20   3   8   n   6   n    8   
p[i]   0   1   6   1   2   8  -1   5  -1    8

The list newReachableVertices becomes [3, 4, 10].
The arrays after the fifth iteration are

  i    1   2   3   4   5   6   7   8   9   10
d[i]   0   2   9  20   3   8   n   6   9    8   
p[i]   0   1   6   1   2   8  -1   5  10    8

The list newReachableVertices becomes [3, 4, 9].
For the sixth iteration assume that vertex 9 is selected in Step 3. The arrays after the sixth iteration are

  i    1   2   3   4   5   6   7   8   9   10
d[i]   0   2   9  20   3   8  11   6   9    8   
p[i]   0   1   6   1   2   8   9   5  10    8

The list newReachableVertices becomes [3, 4, 7].
The arrays after the seventh iteration are

  i    1   2   3   4   5   6   7   8   9   10
d[i]   0   2   9  20   3   8  11   6   9    8   
p[i]   0   1   6   1   2   8   9   5  10    8

The list newReachableVertices becomes [4, 7].
The arrays after the eighth iteration are

  i    1   2   3   4   5   6   7   8   9   10
d[i]   0   2   9  20   3   8  11   6   9    8   
p[i]   0   1   6   1   2   8   9   5  10    8

The list newReachableVertices becomes [4].
The arrays after the ninth iteration are

  i    1   2   3   4   5   6   7   8   9   10
d[i]   0   2   9  20   3   8  11   6   9    8   
p[i]   0   1   6   1   2   8   9   5  10    8

The list newReachableVertices becomes empty and the algorithm terminates.

(c)

The shortest path to vertex 2 is: 1 = p[2], 2.

The shortest path to vertex 3 is: 1, 2, 5, 8, 6, 3.

The shortest path to vertex 4 is: 1, 4.

The shortest path to vertex 5 is: 1, 2, 5.

The shortest path to vertex 6 is: 1, 2, 5, 8, 6.

The shortest path to vertex 7 is: 1, 2, 5, 8, 10, 9, 7.

The shortest path to vertex 8 is: 1, 2, 5, 8.

The shortest path to vertex 9 is: 1, 2, 5, 8, 10, 9.

The shortest path to vertex 10 is: 1, 2, 5, 8, 10.