Java Reference
In-Depth Information
Pedagogical Note
active program to find a shortest path between any two cities, as shown in Figure 29.20.
shortest path animation on
Companion Website
F
IGURE
29.20
The animation tool displays a shortest path between two cities.
Listing 29.8 gives a test program that displays the shortest paths from Chicago to all other
cities in Figure 29.1 and the shortest paths from vertex
3
to all vertices for the graph in
Figure 29.3a, respectively.
L
ISTING
29.8
TestShortestPath.java
1
public class
TestShortestPath {
2
public static void
main(String[] args) {
3 String[] vertices = {
"Seattle"
,
"San Francisco"
,
"Los Angeles"
,
4
vertices
"Denver"
,
"Kansas City"
,
"Chicago"
,
"Boston"
,
"New York"
,
5
"Atlanta"
,
"Miami"
,
"Dallas"
,
"Houston"
};
6
7
int
[][] edges = {
8 {
0
,
1
,
807
}, {
0
,
3
,
1331
}, {
0
,
5
,
2097
},
9 {
1
,
0
,
807
}, {
1
,
2
,
381
}, {
1
,
3
,
1267
},
10 {
2
,
1
,
381
}, {
2
,
3
,
1015
}, {
2
,
4
,
1663
}, {
2
,
10
,
1435
},
11 {
3
,
0
,
1331
}, {
3
,
1
,
1267
}, {
3
,
2
,
1015
}, {
3
,
4
,
599
},
12 {
3
,
5
,
1003
},
13 {
4
,
2
,
1663
}, {
4
,
3
,
599
}, {
4
,
5
,
533
}, {
4
,
7
,
1260
},
14 {
4
,
8
,
864
}, {
4
,
10
,
496
},
15 {
5
,
0
,
2097
}, {
5
,
3
,
1003
}, {
5
,
4
,
533
},
16 {
5
,
6
,
983
}, {
5
,
7
,
787
},
17 {
6
,
5
,
983
}, {
6
,
7
,
214
},
18 {
7
,
4
,
1260
}, {
7
,
5
,
787
}, {
7
,
6
,
214
}, {
7
,
8
,
888
},
19 {
8
,
4
,
864
}, {
8
,
7
,
888
}, {
8
,
9
,
661
},
20 {
8
,
10
,
781
}, {
8
,
11
,
810
},
21 {
9
,
8
,
661
}, {
9
,
11
,
1187
},
edges
Search WWH ::
Custom Search