WEIGHTED GRAPHS AND APPLICATIONS - Introduction to Java Programming: Comprehensive Version - page 1086

The program creates a weighted graph for Figure 29.1 in line 27. It then invokes the
getShortestPath(graph1.getIndex("Chicago")) method to return a Path
object that contains all shortest paths from Chicago. Invoking printAllPaths() on the
ShortestPathTree object displays all the paths (line 30).
The graphical illustration of all shortest paths from Chicago is shown in Figure 29.21. The
shortest paths from Chicago to the cities are found in this order: Kansas City, New York,
Boston, Denver, Dallas, Houston, Atlanta, Los Angeles, Miami, Seattle, and San Francisco.

Seattle

10

2097

Boston

3

983

Chicago

1331 214

2

807

1003

787

New York

Denver

533

4

1267 1260

11

599

888

San Francisco

1

1015

Kansas City

381 1663

864

8

7

496

Los Angeles

1435

Atlanta

5

781

810

Dallas

661

6

239

Houston

1187

9

Miami

F IGURE 29.21

The shortest paths from Chicago to all other cities are highlighted.

29.9

✓ ✓

Trace Dijkstra's algorithm for finding shortest paths from Boston to all other cities in
Figure 29.1.

Check

Point

29.10

Is a shortest path between two vertices unique if all edges have different weights?

29.11

If you use an adjacency matrix to represent weighted edges, what would be the time
complexity for Dijkstra's algorithm?

29.12

What happens to the getShortestPath() method in WeightedGraph if the source
vertex cannot reach all vertieces in the graph? Verify your answer by writing a test
program that creates an unconnected graph and invoke the getShortestPath()
method. How do you fix the problem by obtaining a partial shortest path tree?

29.13

If there is no path from vertex v to the source vertex, what will be cost[v] ?

29.14

Assume that the graph is connected; will the getShortestPath method find the
shortest paths correctly if lines 159-161 in WeightedGraph are deleted?

29.6 Case Study: The Weighted Nine Tails Problem
The weighted nine tails problem can be reduced to the weighted shortest path problem.

Key
Point

Section 28.10 presented the nine tails problem and solved it using the BFS algorithm. This
section presents a variation of the problem and solves it using the shortest-path algorithm.