Java Reference
In-Depth Information
202
203
/** Construct a path */
204
public
ShortestPathTree(
int
source,
int
[] parent,
205 List<Integer> searchOrder,
double
[] cost) {
206
constructor
super
(source, parent, searchOrder);
207
this
.cost = cost;
208 }
209
210
/** Return the cost for a path from the root to vertex v */
get cost
211
public double
getCost(
int
v) {
212
return
cost[v];
213 }
214
215
/** Print paths from all vertices to the source */
216
public void
printAllPaths() {
217 System.out.println(
"All shortest paths from "
+
218 vertices.get(getRoot()) +
" are:"
);
219
for
(
int
i =
0
; i < cost.length; i++) {
220 printPath(i);
// Print a path from i to the source
221 System.out.println(
"(cost: "
+ cost[i] +
")"
);
// Path cost
222 }
223 }
224 }
225 }
print all paths
The
WeightedGraph
class extends the
AbstractGraph
class (line 3). The properties
vertices
and
neighbors
in
AbstractGraph
are inherited in
WeightedGraph
.
neighbors
is a list. Each element is the list is another list that contains edges. For unweighted
graph, each edge is an instance of
AbstractGraph.Edge
. For a weighted graph, each edge
is an instance of
WeightedEdge
.
WeightedEdge
is a subtype of
Edge
. So you can add a
weighted edge into
neighbors.get(i)
for a weighted graph (line 47).
Listing 29.3 gives a test program that creates a graph for the one in Figure 29.1 and another
graph for the one in Figure 29.3a.
L
ISTING
29.3
TestWeightedGraph.java
1
public class
TestWeightedGraph {
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
},
22 {
10
,
2
,
1435
}, {
10
,
4
,
496
}, {
10
,
8
,
781
}, {
10
,
11
,
239
},
23 {
11
,
8
,
810
}, {
11
,
9
,
1187
}, {
11
,
10
,
239
}
edges
Search WWH ::
Custom Search