586
Graph Algorithms
great as the d value of y when y was brought into IN. Therefore there cannot be a
shorter path from x to y via z because there is not even a shorter path just between
x and z.
praCtiCe 12 Trace Dijkstra’s algorithm on the graph shown in Figure 7.10. Show the values for p and IN
and the d values and s values for each pass through the while loop. Write out the nodes of
the shortest path and the distance of the path.
Figure 7.10
When looking for the next node to bring into IN in Dijkstra’s algorithm, more
than one node p may have a minimum d value, in which case p can be selected arbitrarily. There may also be more than one shortest path between x and y in a graph.
Dijkstra’s algorithm also works for directed graphs if the adjacency matrix is
in the appropriate form. And it works for unconnected graphs; if x and y are not
in the same component, then d 3 y 4 will remain ∞ throughout. After y has been
brought into IN, the algorithm will terminate, and this value of ∞ for d3 y 4 will
indicate that no path exists between x and y.
We may think of Dijkstra’s algorithm as being a “nearsighted” algorithm. It
cannot see the entire graph at once to pick out overall shortest paths; it only picks
out shortest paths relative to the set IN at each step. Such an algorithm is called
a greedy algorithm—it does what seems best based on its limited immediate
knowledge. In this case, what seems best at the time turns out to be best overall.
How efficient is Dijkstra’s algorithm? Most of the work seems to take place
within the for loop that modifies the d and s arrays. Here the algorithm checks
all n nodes to determine which nodes z are not in IN and recomputes d3z 4 for
those nodes, possibly also changing s 3z 4. The necessary quantities d3z 4, d3 p 4, and
a3 p, z 4 for a given z are directly available. Therefore the for loop requires Θ(n)
operations. In addition, determining the node p to add to IN can also be done in
Θ(n) operations by checking all n nodes. With the additional small amount of
work to add p to IN, each execution of the while loop takes Θ(n) operations. In the
worst case, y is the last node brought into IN, and the while loop will be executed
n − 1 times. Therefore the total number of operations involved in the while loop
is Θ(n(n − 1)) = Θ(n
2
). Initialization and writing the output together take Θ(n)
operations, so the algorithm requires Θ(n + n
2
) = Θ(n
2
) operations in the worst
case.
What if we keep IN (or rather the complement of IN) as some sort of linked
list, so that all the nodes of the graph do not have to be examined to see which
are not in IN? Surely this would make the algorithm more efficient. Note that the
number of nodes not in IN is initially n − 1, and that number decreases by 1 for
each pass through the while loop. Within the while loop the algorithm thus has to
■
Graph Algorithms
great as the d value of y when y was brought into IN. Therefore there cannot be a
shorter path from x to y via z because there is not even a shorter path just between
x and z.
praCtiCe 12 Trace Dijkstra’s algorithm on the graph shown in Figure 7.10. Show the values for p and IN
and the d values and s values for each pass through the while loop. Write out the nodes of
the shortest path and the distance of the path.
Figure 7.10
When looking for the next node to bring into IN in Dijkstra’s algorithm, more
than one node p may have a minimum d value, in which case p can be selected arbitrarily. There may also be more than one shortest path between x and y in a graph.
Dijkstra’s algorithm also works for directed graphs if the adjacency matrix is
in the appropriate form. And it works for unconnected graphs; if x and y are not
in the same component, then d 3 y 4 will remain ∞ throughout. After y has been
brought into IN, the algorithm will terminate, and this value of ∞ for d3 y 4 will
indicate that no path exists between x and y.
We may think of Dijkstra’s algorithm as being a “nearsighted” algorithm. It
cannot see the entire graph at once to pick out overall shortest paths; it only picks
out shortest paths relative to the set IN at each step. Such an algorithm is called
a greedy algorithm—it does what seems best based on its limited immediate
knowledge. In this case, what seems best at the time turns out to be best overall.
How efficient is Dijkstra’s algorithm? Most of the work seems to take place
within the for loop that modifies the d and s arrays. Here the algorithm checks
all n nodes to determine which nodes z are not in IN and recomputes d3z 4 for
those nodes, possibly also changing s 3z 4. The necessary quantities d3z 4, d3 p 4, and
a3 p, z 4 for a given z are directly available. Therefore the for loop requires Θ(n)
operations. In addition, determining the node p to add to IN can also be done in
Θ(n) operations by checking all n nodes. With the additional small amount of
work to add p to IN, each execution of the while loop takes Θ(n) operations. In the
worst case, y is the last node brought into IN, and the while loop will be executed
n − 1 times. Therefore the total number of operations involved in the while loop
is Θ(n(n − 1)) = Θ(n
2
). Initialization and writing the output together take Θ(n)
operations, so the algorithm requires Θ(n + n
2
) = Θ(n
2
) operations in the worst
case.
What if we keep IN (or rather the complement of IN) as some sort of linked
list, so that all the nodes of the graph do not have to be examined to see which
are not in IN? Surely this would make the algorithm more efficient. Note that the
number of nodes not in IN is initially n − 1, and that number decreases by 1 for
each pass through the while loop. Within the while loop the algorithm thus has to
■