Java Reference
In-Depth Information
Seattle
2097
Boston
1
983
Chicago
9
1331
214
807
8
1003
787
New York
7
Denver
533
1267
1260
599
3
888
4
San Francisco
1015
Kansas City
2
1663
381
864
496
1435
10
Atlanta
Los Angeles
5
781
810
Dallas
661
6
239
Houston
1187
11
Miami
F
IGURE
29.9
The edges in a minimum spanning tree for the cities are highlighted.
✓
✓
29.5
Find a minimum spanning tree for the following graph.
Check
Point
1
10
2
5
7
7
8
0
2
10
6
3
5
7
7
8
5
2
4
29.6
Is a minimum spanning tree unique if all edges have different weights?
29.7
If you use an adjacency matrix to represent weighted edges, what will be the time
complexity for Prim's algorithm?
29.8
What happens to the
getMinimumSpanningTree()
method in
WeightedGraph
if the graph is not connected? Verify your answer by writing a test program that cre-
ates an unconnected graph and invokes the
getMinimumSpanningTree()
method.
How do you fix the problem by obtaining a partial MST?
The shortest path between two vertices is a path with the minimum total weights.
Key
Point
Given a graph with nonnegative weights on the edges, a well-known algorithm for finding a
shortest path
between two vertices was discovered by Edsger Dijkstra, a Dutch computer sci-
entist. In order to find a shortest path from vertex
s
to vertex
v
,
Dijkstra's algorithm
finds the
shortest path
Dijkstra's algorithm
Search WWH ::
Custom Search