Analysis of Algorithms : An Active Learning Approach

6.5 SHORTEST-PATH ALGORITHM 167

In the example in Fig. 6.8, we have the full shortest-path tree for node A

because our destination node was the last to be added. If we had reached node

G earlier, the algorithm would have stopped at that point. There are applica-

tions where we might be interested in the shortest path from one node to

every other node. For example, if we have a small computer network that has

relatively stable transmission rates between the nodes, we could calculate the

shortest path to every other node for each computer. Then when a message

needs to be sent, we would not need to do anything but access our predeter-

mined shortest-path table to find the quickest way to send the message.

6.5.2

1. Execute the shortest-path algorithm on the following graphs starting at
   node A to create the entire shortest-path tree for each one. Count how
   many edges you look at in the process (if you look at one edge more than
   once, count it each time).

■6.5.2 EXERCISES

A B C

F G H

D E

4

11

1

2

2

2

5

4

4

4

4

2

2

2

3

3 3

35

(^366)
a. b. A B
DE
FG
C
A B C
F G H
D E
45
4
1
22
5 24
1
1
4
2
1
3
2
2
3
5
5
(^223)
c. d. A B
DE
G H
C
F
2