1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package org.rblasch.convert.dijkstra;
17
18 import org.rblasch.convert.graph.Connection;
19 import org.rblasch.convert.graph.Edge;
20 import org.rblasch.convert.graph.ListPath;
21 import org.rblasch.convert.graph.Path;
22 import org.rblasch.convert.graph.Vertex;
23 import org.rblasch.convert.graph.WeightedDirectedGraph;
24 import org.rblasch.convert.graph.WeightedEdge;
25
26 import java.util.Collections;
27 import java.util.Comparator;
28 import java.util.HashMap;
29 import java.util.HashSet;
30 import java.util.Iterator;
31 import java.util.LinkedList;
32 import java.util.List;
33 import java.util.Map;
34 import java.util.Set;
35
36 /***
37 * An implementation of Dijkstra's shortest path algorithm. It computes the shortest path (in distance)
38 * to all cities in the map. The output of the algorithm is the shortest distance from the start vertex
39 * to every other vertex, and the shortest path from the start vertex to every other.
40 * <p/>
41 * Upon calling
42 * {@link #execute(Vertex, Vertex)},
43 * the results of the algorithm are made available by calling
44 * {@link #getPredecessor(Vertex)}
45 * and
46 * {@link #getShortestDistance(Vertex)}.
47 * <p/>
48 * To get the shortest path between the vertex <var>destination</var> and
49 * the source vertex after running the algorithm, one would do:
50 * <pre>
51 * List l = new ArrayList();
52 * <p/>
53 * for (Object vertex = destination; vertex != null; vertex = engine.getPredecessor(vertex))
54 * {
55 * l.add(vertex);
56 * }
57 * <p/>
58 * Collections.reverse(l);
59 * <p/>
60 * return l;
61 * </pre>
62 *
63 * @author Renaud Waldura <renaud+tw@waldura.com>
64 * @version $Id: DijkstraEngine.java,v 1.4 2003/03/03 01:26:22 renaud Exp $
65 * @see #execute(Vertex, Vertex)
66 */
67 public class ShortestPathEngine {
68 /***
69 * Infinity value for distances.
70 */
71 public static final int INFINITE_DISTANCE = Integer.MAX_VALUE;
72
73 /***
74 * This comparator orders cities according to their shortest distances,
75 * in ascending fashion. If two cities have the same shortest distance,
76 * we compare the cities themselves.
77 */
78 private final Comparator shortestDistanceComparator = new Comparator() {
79 public int compare(final Object left, final Object right) {
80
81 return getShortestDistance((Vertex) left) - getShortestDistance((Vertex) right);
82 }
83 };
84
85 /***
86 * The graph.
87 */
88 private final WeightedDirectedGraph graph;
89
90 /***
91 * The working set of cities, kept ordered by shortest distance.
92 */
93 private final Set
94
95 /***
96 * The set of cities for which the shortest distance to the source
97 * has been found.
98 */
99 private final Set
100
101 /***
102 * The currently known shortest distance for all vertices.
103 */
104 private final Map
105
106 /***
107 * Predecessors list: maps a vertex to its predecessor in the spanning tree of
108 * shortest paths.
109 */
110 private final Map
111
112 /***
113 * Constructor.
114 */
115 public ShortestPathEngine(final WeightedDirectedGraph map) {
116 this.graph = map;
117 }
118
119 /***
120 * Initialize all data structures used by the algorithm.
121 *
122 * @param start the source node
123 */
124 private void init(final Vertex start) {
125 settledNodes.clear();
126 unsettledNodes.clear();
127
128 shortestDistances.clear();
129 predecessors.clear();
130
131
132 setShortestDistance(start, 0);
133 unsettledNodes.add(start);
134 }
135
136 /***
137 * Run Dijkstra's shortest path algorithm on the map.
138 * The results of the algorithm are available through
139 * {@link #getPredecessor(Vertex)}
140 * and
141 * {@link #getShortestDistance(Vertex)}
142 * upon completion of this method.
143 *
144 * @param start the starting vertex
145 * @param destination the destination vertex. If this argument is <code>null</code>, the algorithm is
146 * run on the entire graph, instead of being stopped as soon as the destination is reached.
147 */
148 public void execute(final Vertex start, final Vertex destination) {
149 init(start);
150
151
152 Vertex u;
153
154
155 while ((u = extractMin()) != null) {
156
157
158
159 if (u == destination) break;
160
161 markSettled(u);
162
163 relaxNeighbors(u);
164 }
165 }
166
167 public Path getShortestPath(final Vertex start, final Vertex end) {
168 execute(start, end);
169
170 final List
171 if (getShortestDistance(end) == ShortestPathEngine.INFINITE_DISTANCE) {
172 return null;
173 }
174 Vertex nextVertex = end;
175 path.add(nextVertex);
176 while (nextVertex != null) {
177 final Vertex vertex = getPredecessor(nextVertex);
178 if (vertex != null) {
179 path.add(getMinWeightEdge(vertex, nextVertex));
180 path.add(vertex);
181 }
182 nextVertex = vertex;
183 }
184
185 Collections.reverse(path);
186
187 return new ListPath(path);
188 }
189
190 private Edge getMinWeightEdge(final Vertex start, final Vertex end) {
191 return ((WeightedEdge) ((Connection) Collections.min(graph.getConnections(start, end), new Comparator() {
192 public int compare(final Object o1, final Object o2) {
193 final Connection c1 = (Connection) o1;
194 final Connection c2 = (Connection) o2;
195
196 return new Integer(((WeightedEdge) c1.getEdge()).getWeight()).compareTo(new Integer(((WeightedEdge) c2.getEdge()).getWeight()));
197 }
198 })).getEdge());
199 }
200
201 /***
202 * Get the value of a segment.
203 */
204 public int getMinWeight(final Vertex start, final Vertex end) {
205 return ((WeightedEdge) getMinWeightEdge(start, end)).getWeight();
206 }
207
208 /***
209 * Extract the vertex with the currently shortest distance, and remove it from
210 * the priority queue.
211 *
212 * @return the minimum vertex, or <code>null</code> if the queue is empty.
213 */
214 private Vertex extractMin() {
215 if (unsettledNodes.isEmpty()) return null;
216
217 final Object min = Collections.min(unsettledNodes, shortestDistanceComparator);
218 unsettledNodes.remove(min);
219
220 return (Vertex) min;
221 }
222
223 /***
224 * Compute new shortest distance for neighboring nodes and update if a better
225 * distance is found.
226 *
227 * @param u the node
228 */
229 private void relaxNeighbors(final Vertex u) {
230 for (Iterator i = graph.getOutbound(u).iterator(); i.hasNext();) {
231 final Vertex v = (Vertex) i.next();
232
233
234 if (isSettled(v)) continue;
235
236 if (getShortestDistance(v) > getShortestDistance(u) + getMinWeight(u, v)) {
237
238 setShortestDistance(v, getShortestDistance(u) + getMinWeight(u, v));
239
240
241 setPredecessor(v, u);
242 }
243 }
244 }
245
246 /***
247 * Mark a node as settled.
248 *
249 * @param u the node
250 */
251 private void markSettled(final Vertex u) {
252 settledNodes.add(u);
253 }
254
255 /***
256 * Test a node.
257 *
258 * @param v the node to consider
259 * @return whether the node is settled, ie. its shortest distance
260 * has been found.
261 */
262 private boolean isSettled(final Vertex v) {
263 return settledNodes.contains(v);
264 }
265
266 /***
267 * @return the shortest distance from the source to the given vertex, or
268 * {@link ShortestPathEngine#INFINITE_DISTANCE} if there is no route to the destination.
269 */
270 public int getShortestDistance(final Vertex vertex) {
271 final Number d = (Number) shortestDistances.get(vertex);
272 return (d == null) ? INFINITE_DISTANCE : d.intValue();
273 }
274
275 /***
276 * Set the new shortest distance for the given node,
277 * and re-balance the set according to new shortest distances.
278 *
279 * @param vertex the node to set
280 * @param distance new shortest distance value
281 */
282 private void setShortestDistance(final Vertex vertex, final int distance) {
283
284
285 unsettledNodes.remove(vertex);
286
287 shortestDistances.put(vertex, new Integer(distance));
288
289
290
291 unsettledNodes.add(vertex);
292 }
293
294 /***
295 * @return the vertex leading to the given vertex on the shortest path, or
296 * <code>null</code> if there is no route to the destination.
297 */
298 public Vertex getPredecessor(final Vertex vertex) {
299 return (Vertex) predecessors.get(vertex);
300 }
301
302 private void setPredecessor(final Vertex a, final Vertex b) {
303 predecessors.put(a, b);
304 }
305 }