class PathVertexInfo implements Comparable
public class DijkstrasDemo
1: //DijkstrasDemo.java
3: import java.lang.Comparable;
4: import java.util.HashMap;
5: import java.util.PriorityQueue;
7: // Stores vertex information that is relevant to a shortest path algorithm
8: class PathVertexInfo implements Comparable<PathVertexInfo>
9: {
10: public Vertex vertex;
11: public double distance;
12: public Vertex predecessor;
14: public PathVertexInfo(Vertex vertex)
15: {
16: this.vertex = vertex;
17: distance = Double.POSITIVE_INFINITY;
18: predecessor = null;
19: }
21: public int compareTo(PathVertexInfo other)
22: {
23: if (distance > other.distance)
24: {
25: return 1;
26: }
27: else if (distance < other.distance)
28: {
29: return -1;
30: }
31: return 0;
32: }
33: }
35: public class DijkstrasDemo
36: {
37: public static HashMap<Vertex, PathVertexInfo> dijkstraShortestPath
38: (
39: Graph graph,
40: Vertex startVertex
41: )
42: {
43: // Create the HashMap for vertex information
44: HashMap<Vertex, PathVertexInfo> info;
45: info = new HashMap<Vertex, PathVertexInfo>();
47: // Put all graph vertices in both the info HashMap and the
48: // PriorityQueue of unvisited vertices
49: PriorityQueue<PathVertexInfo> unvisited;
50: unvisited = new PriorityQueue<PathVertexInfo>();
51: for (Vertex vertex : graph.getVertices())
52: {
53: PathVertexInfo vertexInfo = new PathVertexInfo(vertex);
54: unvisited.add(vertexInfo);
55: info.put(vertex, vertexInfo);
56: }
58: // startVertex has a distance of 0 from itself
59: info.get(startVertex).distance = 0.0;
61: // Iterate through all vertices in the priority queue
62: while (unvisited.size() > 0)
63: {
64: // Get info about the vertex with the shortest distance
65: // from startVertex
66: PathVertexInfo currentInfo = unvisited.peek();
67: unvisited.remove();
69: // Check potential path lengths from the current vertex
70: // to all neighbors
71: for (Edge edge : graph.getEdgesFrom(currentInfo.vertex))
72: {
73: Vertex adjacentVertex = edge.toVertex;
74: double alternativePathDistance =
75: currentInfo.distance + edge.weight;
77: // If a shorter path from startVertex to adjacentVertex is
78: // found, update adjacentVertex's distance and predecessor
79: PathVertexInfo adjacentInfo = info.get(adjacentVertex);
80: if (alternativePathDistance < adjacentInfo.distance)
81: {
82: unvisited.remove(adjacentInfo);
83: adjacentInfo.distance = alternativePathDistance;
84: adjacentInfo.predecessor = currentInfo.vertex;
85: unvisited.add(adjacentInfo);
86: }
87: }
88: }
90: return info;
91: }
93: public static String getShortestPath
94: (
95: Vertex startVertex,
96: Vertex endVertex,
97: HashMap<Vertex,
98: PathVertexInfo> infoMap
99: )
100: {
101: // Start from endVertex and build the path in reverse.
102: String path = "";
103: Vertex currentVertex = endVertex;
104: while (currentVertex != startVertex)
105: {
106: path = " -> " + currentVertex.label + path;
107: currentVertex = infoMap.get(currentVertex).predecessor;
108: }
109: path = startVertex.label + path;
110: return path;
111: }
113: public static void main(String[] args)
114: {
115: Graph g = new Graph();
117: Vertex vertexA = g.addVertex("A");
118: Vertex vertexB = g.addVertex("B");
119: Vertex vertexC = g.addVertex("C");
120: Vertex vertexD = g.addVertex("D");
121: Vertex vertexE = g.addVertex("E");
122: Vertex vertexF = g.addVertex("F");
123: Vertex vertexG = g.addVertex("G");
124: Vertex[] vertices =
125: {
126: vertexA,
127: vertexB,
128: vertexC,
129: vertexD,
130: vertexE,
131: vertexF,
132: vertexG
133: };
135: g.addUndirectedEdge(vertexA, vertexB, 8);
136: g.addUndirectedEdge(vertexA, vertexC, 7);
137: g.addUndirectedEdge(vertexA, vertexD, 3);
138: g.addUndirectedEdge(vertexB, vertexE, 6);
139: g.addUndirectedEdge(vertexC, vertexD, 1);
140: g.addUndirectedEdge(vertexC, vertexE, 2);
141: g.addUndirectedEdge(vertexD, vertexF, 15);
142: g.addUndirectedEdge(vertexD, vertexG, 12);
143: g.addUndirectedEdge(vertexE, vertexF, 4);
144: g.addUndirectedEdge(vertexF, vertexG, 1);
146: // Run Dijkstra's algorithm first.
147: HashMap<Vertex, PathVertexInfo> infoMap =
148: dijkstraShortestPath(g, vertexA);
150: // Display shortest path for each vertex from vertexA.
151: for (Vertex vertex : vertices)
152: {
153: PathVertexInfo info = infoMap.get(vertex);
154: if (info.predecessor == null && vertex != vertexA)
155: {
156: System.out.printf("A to %s: no path exists%n", vertex.label);
157: }
158: else
159: {
160: System.out.printf
161: (
162: "A to %s: %s (total weight: %d)%n",
163: vertex.label,
164: getShortestPath(vertexA, vertex, infoMap),
165: (int)info.distance
166: );
167: }
168: }
169: }
170: }