Analysis of Algorithms : An Active Learning Approach

164 GRAPH ALGORITHMS

clearly not the shortest path, because you can see in Fig. 6.7(a) that there is a

direct path between node A and node B that has length 2.

■ 6.5.1 Dijkstra’s Algorithm
The minimum spanning tree algorithm will not work to find the shortest path
because its greedy algorithm just considered the weight of one edge at each
pass. If we modify the algorithm so that it chooses the edge to the fringe that is
part of the shortest entire path from the starting node, we will get the result we
want. More specifically, our algorithm becomes
select a starting node
build the initial fringe from nodes connected to the starting node
while we are not at the destination node do
choose the fringe node with the shortest path to the starting node
add that node and its edge to the tree
update the fringe by:
adding nodes to the fringe connected to the new node
for each node in the fringe do
update its edge to the one connected to the tree on the shortest
path to the starting node
end for
end while

Figure 6.8 shows an example execution of this algorithm. We begin with

the same graph that we used for the minimum spanning tree algorithm (repro-

duced here as Fig. 6.8(a)) and will look for the shortest path starting at node A

and ending at node G.

A B

F G

C D E

(^47)
7
6
2
6
6
6
1
58
3
F
D
C
B
A
2
4
7
5
■FIGURE 6.8A
The original graph
■FIGURE 6.8B
The shortest path is to
node B