The following codes implement a sample application that uses the Dijkstra algorithm to solve the "shortest path" problem. Edit the sample program to ask the user to input the vertices (cities) for the graph (instead of hardcoding values as they did...Redville, Greenville,...) and then have the user input the distances between the cities (again instead of hardcoding the numbers as they did in the original sample code).

import java.util.PriorityQueue; import java.util.List; import java.util.ArrayList; import java.util.Collections; /////////////// //Vertex class /////////////// class Vertex implements Comparable { public final String name; public Edge[] adjacencies; public double minDistance = Double.POSITIVE_INFINITY; public Vertex previous; public Vertex(String argName) { name = argName; } public String toString() { return name; } public int compareTo(Vertex other) { return Double.compare(minDistance, other.minDistance); } } /////////////// //Edge class /////////////// class Edge { public final Vertex target; public final double weight; public Edge(Vertex argTarget, double argWeight) { target = argTarget; weight = argWeight; } } //////////////////////////////////// // Dijkstra's Shortest path class /////////////////////////////////// public class Dijkstra { public static void computePaths(Vertex source) { source.minDistance = 0.; PriorityQueue vertexQueue = new PriorityQueue(); vertexQueue.add(source); while (!vertexQueue.isEmpty()) { Vertex u = vertexQueue.poll(); // Visit each edge exiting u for (Edge e : u.adjacencies) { Vertex v = e.target; double weight = e.weight; double distanceThroughU = u.minDistance + weight; if (distanceThroughU < v.minDistance) { vertexQueue.remove(v); v.minDistance = distanceThroughU; v.previous = u; vertexQueue.add(v); } } } } public static List getShortestPathTo(Vertex target) { List path = new ArrayList(); for (Vertex vertex = target; vertex != null; vertex = vertex.previous) path.add(vertex); Collections.reverse(path); return path; } }//end Dijkstra class The test code.

import java.util.List; //your class test shortest path public class TestShortestPath { public static void main(String[] args) { Vertex v0 = new Vertex("Redvile"); Vertex v1 = new Vertex("Blueville"); Vertex v2 = new Vertex("Greenville"); Vertex v3 = new Vertex("Orangeville"); Vertex v4 = new Vertex("Purpleville"); v0.adjacencies = new Edge[]{ new Edge(v1, 5), new Edge(v2, 10), new Edge(v3, 8) }; v1.adjacencies = new Edge[]{ new Edge(v0, 5), new Edge(v2, 3), new Edge(v4, 7) }; v2.adjacencies = new Edge[]{ new Edge(v0, 10), new Edge(v1, 3) }; v3.adjacencies = new Edge[]{ new Edge(v0, 8), new Edge(v4, 2) }; v4.adjacencies = new Edge[]{ new Edge(v1, 7), new Edge(v3, 2) }; Vertex[] vertices = { v0, v1, v2, v3, v4 }; Dijkstra.computePaths(v0); for (Vertex v : vertices) { System.out.println("Distance to " + v + ": " + v.minDistance); List path = Dijkstra.getShortestPathTo(v); System.out.println("Path: " + path); } }//end main }//end class