- Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathShortestPaths.java
More file actions
Latest commit
150 lines (128 loc) · 4.92 KB
/
Copy pathShortestPaths.java
File metadata and controls
150 lines (128 loc) · 4.92 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
packagegraph;
/* See restrictions in Graph.java. */
importjava.util.List;
importjava.util.ArrayList;
importjava.util.Comparator;
importjava.util.Collections;
importjava.util.PriorityQueue;
/** The shortest paths through an edge-weighted graph.
* By overrriding methods getWeight, setWeight, getPredecessor, and
* setPredecessor, the client can determine how to represent the weighting
* and the search results. By overriding estimatedDistance, clients
* can search for paths to specific destinations using A* search.
* @author Rafayel Mkrtchyan
*/
publicabstractclassShortestPaths {
/** The shortest paths in G from SOURCE. */
publicShortestPaths(GraphG, intsource) {
this(G, source, 0);
}
/** A shortest path in G from SOURCE to DEST. */
publicShortestPaths(GraphG, intsource, intdest) {
_G = G;
_source = source;
_dest = dest;
Comparator<Integer> compData = newObjCompare();
nextVertices = newPriorityQueue<Integer>(_G.vertexSize(), compData);
}
/** Initialize the shortest paths. Must be called before using
* getWeight, getPredecessor, and pathTo. */
publicvoidsetPaths() {
setWeight(getSource(), 0);
setPredecessor(getSource(), 0);
for (intv : _G.vertices()) {
nextVertices.add(v);
}
while (!nextVertices.isEmpty()) {
intv = nextVertices.remove();
if (v == _dest) {
return;
}
for (intw : _G.successors(v)) {
if (getWeight(v) + getWeight(v, w) < getWeight(w)) {
doublenewWeight = getWeight(v) + getWeight(v, w);
setWeight(w, newWeight);
setPredecessor(w, v);
nextVertices.remove(w);
nextVertices.add(w);
}
}
}
}
/** Returns the starting vertex. */
publicintgetSource() {
return_source;
}
/** Returns the target vertex, or 0 if there is none. */
publicintgetDest() {
return_dest;
}
/** Returns the current weight of vertex V in the graph. If V is
* not in the graph, returns positive infinity. */
publicabstractdoublegetWeight(intv);
/** Set getWeight(V) to W. Assumes V is in the graph. */
protectedabstractvoidsetWeight(intv, doublew);
/** Returns the current predecessor vertex of vertex V in the graph, or 0 if
* V is not in the graph or has no predecessor. */
publicabstractintgetPredecessor(intv);
/** Set getPredecessor(V) to U. */
protectedabstractvoidsetPredecessor(intv, intu);
/** Returns an estimated heuristic weight of the shortest path from vertex
* V to the destination vertex (if any). This is assumed to be less
* than the actual weight, and is 0 by default. */
protecteddoubleestimatedDistance(intv) {
return0.0;
}
/** Returns the current weight of edge (U, V) in the graph. If (U, V) is
* not in the graph, returns positive infinity. */
protectedabstractdoublegetWeight(intu, intv);
/** Returns a list of vertices starting at _source and ending
* at V that represents a shortest path to V. Invalid if there is a
* destination vertex other than V. */
publicList<Integer> pathTo(intv) {
ArrayList<Integer> result = newArrayList<Integer>();
inttemp = v;
result.add(temp);
intdestinationVertex = getSource();
while (temp != destinationVertex) {
result.add(getPredecessor(temp));
temp = getPredecessor(temp);
}
Collections.reverse(result);
returnresult;
}
/** Returns a list of vertices starting at the source and ending at the
* destination vertex. Invalid if the destination is not specified. */
publicList<Integer> pathTo() {
returnpathTo(getDest());
}
/** New comparator class. */
classObjCompareimplementsComparator<Integer> {
/** RETURNS compare method from Comparator Interface
* for Integers O1 and O2. */
@Override
publicintcompare(Integero1, Integero2) {
doublefirstValue = getWeight(o1) + estimatedDistance(o1);
doublesecondValue = getWeight(o2) + estimatedDistance(o2);
if (firstValue == secondValue) {
return0;
}
if (firstValue < secondValue) {
return -1;
}
return1;
}
}
/** The graph being searched. */
protectedfinalGraph_G;
/** The starting vertex. */
privatefinalint_source;
/** The target vertex. */
privatefinalint_dest;
/** RETURNS information about next vertices. */
PriorityQueue<Integer> getnextVertices() {
returnnextVertices;
}
/** Provides information about next vertices. */
privatePriorityQueue<Integer> nextVertices;
}