S e c t i o n 7 . 3 revieW
tecHniQueS
• Find a shortest path from x to y in a graph (using
Dijkstra’s algorithm).
• Find a minimal spanning tree for a graph (using
Prim’s algorithm).
main iDea
• Algorithms that are Θ(n
2
) in the worst case can
find a shortest path between two nodes or a minimal spanning tree in a simple, positively weighted,
connected graph with n nodes.
W
W
exeRciSeS 7.3
For Exercises 1–4, use the graph that follows. Apply Dijkstra’s algorithm for the pairs of nodes given; 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 in
the shortest path and the distance of the path.
1. From 2 to 5
2. From 3 to 6
3. From 1 to 5
4. From 4 to 7
For Exercises 5 and 6, use the graph that follows. Apply Dijkstra’s algorithm for the pairs of nodes given; 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
in the shortest path and the distance of the path.
3
2
1
1
1
2
1
1
4
a
f
c
d
b
e
5. From a to e
6. From d to a
Section 7.3 Shortest Path and Minimal Spanning Tree
591