View Javadoc

1   /*
2    * Copyright 2004 Ronald Blaschke.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
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 &lt;renaud+tw@waldura.com&gt;
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              // note that this trick doesn't work for huge distances, close to Integer.MAX_VALUE
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 /* of Vertex */ unsettledNodes = new HashSet();
94  
95      /***
96       * The set of cities for which the shortest distance to the source
97       * has been found.
98       */
99      private final Set /* of Vertex */ settledNodes = new HashSet();
100 
101     /***
102      * The currently known shortest distance for all vertices.
103      */
104     private final Map /* of Vertex -> Integer */ shortestDistances = new HashMap();
105 
106     /***
107      * Predecessors list: maps a vertex to its predecessor in the spanning tree of
108      * shortest paths.
109      */
110     private final Map /* of Vertex -> Vertex */ predecessors = new HashMap();
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         // add source
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         // the current node
152         Vertex u;
153 
154         // extract the node with the shortest distance
155         while ((u = extractMin()) != null) {
156             //assert !isSettled(u);
157 
158             // destination reached, stop
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 /* of Vertex, Edge */ path = new LinkedList();
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             // skip node already settled
234             if (isSettled(v)) continue;
235 
236             if (getShortestDistance(v) > getShortestDistance(u) + getMinWeight(u, v)) {
237                 // assign new shortest distance and mark unsettled
238                 setShortestDistance(v, getShortestDistance(u) + getMinWeight(u, v));
239 
240                 // assign predecessor in shortest path
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         // this crucial step ensure no duplicates will be created in the queue
284         // when an existing unsettled node is updated with a new shortest distance
285         unsettledNodes.remove(vertex);
286 
287         shortestDistances.put(vertex, new Integer(distance));
288 
289         // re-balance the sorted set according to the new shortest distance found
290         // (see the comparator the set was initialized with)
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 }