Analysis of Algorithms : An Active Learning Approach

166 GRAPH ALGORITHMS

of the other connections, we now choose node F to get Fig. 6.8(f ). You should

see that even though the selection of node F changed the edge for node D, if

we had selected node F first, we would have chosen node E second.

In Fig. 6.8(f ), it should be clear that the path to node D is shorter than the path

to node G. Choosing node D results in Fig. 6.8(g), and then node G is the last to

be added, giving the final shortest path tree in Fig. 6.8(h). The shortest path from

node A to node G has length of 10. If you look back at Fig. 6.5(h), you will see

another example of the minimum spanning tree not having the shortest path,

because that figure has the path from node A to node G at length 11.

4

7

5

2

3

8

D

F

G

E

C

B

A

4

5

2

3

8

A F^1

D

C

B G

E

■FIGURE 6.8E

The other path of length 5 to node F

is next

■FIGURE 6.8F

The path of length 6 to node D is shorter

than the path to node G

4

5

2

3

8

A F^1 D

C

B G

E

4

5

2

3

8

1

A F

D

C

G

B

E

■FIGURE 6.8G

The path to node G is the only

one left

■FIGURE 6.8H

The complete shortest

path tree starting at node A