KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > alg > DijkstraShortestPath


1 /* ==========================================
2  * JGraphT : a free Java graph-theory library
3  * ==========================================
4  *
5  * Project Info: http://jgrapht.sourceforge.net/
6  * Project Creator: Barak Naveh (http://sourceforge.net/users/barak_naveh)
7  *
8  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9  *
10  * This library is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation; either version 2.1 of the License, or
13  * (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful, but
16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this library; if not, write to the Free Software Foundation,
22  * Inc.,
23  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24  */
25 /* -------------------------
26  * DijkstraShortestPath.java
27  * -------------------------
28  * (C) Copyright 2003-2006, by John V. Sichi and Contributors.
29  *
30  * Original Author: John V. Sichi
31  * Contributor(s): Christian Hammer
32  *
33  * $Id: DijkstraShortestPath.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 02-Sep-2003 : Initial revision (JVS);
38  * 29-May-2005 : Make non-static and add radius support (JVS);
39  * 07-Jun-2005 : Made generic (CH);
40  *
41  */
42 package org.jgrapht.alg;
43
44 import java.util.*;
45
46 import org.jgrapht.*;
47 import org.jgrapht.traverse.*;
48
49
50 /**
51  * An implementation of <a
52  * HREF="http://mathworld.wolfram.com/DijkstrasAlgorithm.html">Dijkstra's
53  * shortest path algorithm</a> using <code>ClosestFirstIterator</code>.
54  *
55  * @author John V. Sichi
56  * @since Sep 2, 2003
57  */
58 public final class DijkstraShortestPath<V, E>
59 {
60
61     //~ Instance fields -------------------------------------------------------
62
63     private List<E> edgeList;
64     private double pathLength;
65
66     //~ Constructors ----------------------------------------------------------
67
68     /**
69      * Creates and executes a new DijkstraShortestPath algorithm instance. An
70      * instance is only good for a single search; after construction, it can be
71      * accessed to retrieve information about the path found.
72      *
73      * @param graph the graph to be searched
74      * @param startVertex the vertex at which the path should start
75      * @param endVertex the vertex at which the path should end
76      */
77     public DijkstraShortestPath(Graph<V, E> graph,
78         V startVertex,
79         V endVertex)
80     {
81         this(graph, startVertex, endVertex, Double.POSITIVE_INFINITY);
82     }
83
84     /**
85      * Creates and executes a new DijkstraShortestPath algorithm instance. An
86      * instance is only good for a single search; after construction, it can be
87      * accessed to retrieve information about the path found.
88      *
89      * @param graph the graph to be searched
90      * @param startVertex the vertex at which the path should start
91      * @param endVertex the vertex at which the path should end
92      * @param radius limit on path length, or Double.POSITIVE_INFINITY for
93      * unbounded search
94      */
95     public DijkstraShortestPath(
96         Graph<V, E> graph,
97         V startVertex,
98         V endVertex,
99         double radius)
100     {
101         ClosestFirstIterator<V, E> iter =
102             new ClosestFirstIterator<V, E>(graph, startVertex, radius);
103
104         while (iter.hasNext()) {
105             V vertex = iter.next();
106
107             if (vertex.equals(endVertex)) {
108                 createEdgeList(graph, iter, endVertex);
109                 pathLength = iter.getShortestPathLength(endVertex);
110
111                 return;
112             }
113         }
114
115         edgeList = null;
116         pathLength = Double.POSITIVE_INFINITY;
117     }
118
119     //~ Methods ---------------------------------------------------------------
120
121     /**
122      * Return the edges making up the path found.
123      *
124      * @return List of Edges, or null if no path exists
125      */
126     public List<E> getPathEdgeList()
127     {
128         return edgeList;
129     }
130
131     /**
132      * Return the length of the path found.
133      *
134      * @return path length, or Double.POSITIVE_INFINITY if no path exists
135      */
136     public double getPathLength()
137     {
138         return pathLength;
139     }
140
141     /**
142      * Convenience method to find the shortest path via a single static method
143      * call. If you need a more advanced search (e.g. limited by radius, or
144      * computation of the path length), use the constructor instead.
145      *
146      * @param graph the graph to be searched
147      * @param startVertex the vertex at which the path should start
148      * @param endVertex the vertex at which the path should end
149      *
150      * @return List of Edges, or null if no path exists
151      */
152     public static <V, E> List<E> findPathBetween(
153         Graph<V, E> graph,
154         V startVertex,
155         V endVertex)
156     {
157         DijkstraShortestPath<V, E> alg =
158             new DijkstraShortestPath<V, E>(
159                 graph,
160                 startVertex,
161                 endVertex);
162
163         return alg.getPathEdgeList();
164     }
165
166     private void createEdgeList(
167         Graph<V, E> graph,
168         ClosestFirstIterator<V, E> iter,
169         V endVertex)
170     {
171         edgeList = new ArrayList<E>();
172
173         while (true) {
174             E edge = iter.getSpanningTreeEdge(endVertex);
175
176             if (edge == null) {
177                 break;
178             }
179
180             edgeList.add(edge);
181             endVertex = Graphs.getOppositeVertex(graph, edge, endVertex);
182         }
183
184         Collections.reverse(edgeList);
185     }
186 }
187
Popular Tags