Download code

Jump to: navigation, search

Back to Dijkstra's_algorithm_(Java)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

Dijkstra.java

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Dijkstra's_algorithm_(Java)?oldid=15444
 14 */
 15 
 16 import java.util.PriorityQueue;
 17 import java.util.List;
 18 import java.util.ArrayList;
 19 import java.util.Collections;
 20 
 21 class Vertex implements Comparable<Vertex>
 22 {
 23     public final String name;
 24     public Edge[] adjacencies;
 25     public double minDistance = Double.POSITIVE_INFINITY;
 26     public Vertex previous;
 27     public Vertex(String argName) { name = argName; }
 28     public String toString() { return name; }
 29     public int compareTo(Vertex other)
 30     {
 31         return Double.compare(minDistance, other.minDistance);
 32     }
 33 
 34 }
 35 
 36 
 37 class Edge
 38 {
 39     public final Vertex target;
 40     public final double weight;
 41     public Edge(Vertex argTarget, double argWeight)
 42     { target = argTarget; weight = argWeight; }
 43 }
 44 
 45 public class Dijkstra
 46 {
 47     public static void computePaths(Vertex source)
 48     {
 49         source.minDistance = 0.;
 50         PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
 51 	vertexQueue.add(source);
 52 
 53 	while (!vertexQueue.isEmpty()) {
 54 	    Vertex u = vertexQueue.poll();
 55 
 56             // Visit each edge exiting u
 57             for (Edge e : u.adjacencies)
 58             {
 59                 Vertex v = e.target;
 60                 double weight = e.weight;
 61                 double distanceThroughU = u.minDistance + weight;
 62 		if (distanceThroughU < v.minDistance) {
 63 		    vertexQueue.remove(v);
 64 
 65 		    v.minDistance = distanceThroughU ;
 66 		    v.previous = u;
 67 		    vertexQueue.add(v);
 68 		}
 69             }
 70         }
 71     }
 72 
 73     public static List<Vertex> getShortestPathTo(Vertex target)
 74     {
 75         List<Vertex> path = new ArrayList<Vertex>();
 76         for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
 77             path.add(vertex);
 78 
 79         Collections.reverse(path);
 80         return path;
 81     }
 82 
 83     public static void main(String[] args)
 84     {
 85         Vertex v0 = new Vertex("Harrisburg");
 86 	Vertex v1 = new Vertex("Baltimore");
 87 	Vertex v2 = new Vertex("Washington");
 88 	Vertex v3 = new Vertex("Philadelphia");
 89 	Vertex v4 = new Vertex("Binghamton");
 90 	Vertex v5 = new Vertex("Allentown");
 91 	Vertex v6 = new Vertex("New York");
 92 	v0.adjacencies = new Edge[]{ new Edge(v1,  79.83),
 93 	                             new Edge(v5,  81.15) };
 94 	v1.adjacencies = new Edge[]{ new Edge(v0,  79.75),
 95 	                             new Edge(v2,  39.42),
 96 	                             new Edge(v3, 103.00) };
 97 	v2.adjacencies = new Edge[]{ new Edge(v1,  38.65) };
 98 	v3.adjacencies = new Edge[]{ new Edge(v1, 102.53),
 99 	                             new Edge(v5,  61.44),
100 	                             new Edge(v6,  96.79) };
101 	v4.adjacencies = new Edge[]{ new Edge(v5, 133.04) };
102 	v5.adjacencies = new Edge[]{ new Edge(v0,  81.77),
103 	                             new Edge(v3,  62.05),
104 	                             new Edge(v4, 134.47),
105 	                             new Edge(v6,  91.63) };
106 	v6.adjacencies = new Edge[]{ new Edge(v3,  97.24),
107 	                             new Edge(v5,  87.94) };
108 	Vertex[] vertices = { v0, v1, v2, v3, v4, v5, v6 };
109 
110         computePaths(v0);
111         for (Vertex v : vertices)
112 	{
113 	    System.out.println("Distance to " + v + ": " + v.minDistance);
114 	    List<Vertex> path = getShortestPathTo(v);
115 	    System.out.println("Path: " + path);
116 	}
117     }
118 }


hijacker
hijacker
hijacker
hijacker