You should write a method named findDistances with the following signature: publ

Question

You should write a method named findDistances with the following signature:

public static Map<String, Double> findDistances(String start, Map<String,List<Path>> adj_list)

This method takes a start node name and the adjacency list you built in Part I as arguments and returns a new Map of node names and distances. The keys in this Map are destination city names, and the values in this map are the shortest distances from the start city to the key city, as determined by the shortest path algorithm given in the Overview above.

Your program should also contain a method named displayDistances with the following signature:

public static void displayShortest(String start, Map<String, Double> shortest)

This method displays the shortest distances constructed by findDistances as a nicely formatted report. For example, the shortest paths from the graph above using Seattle as a start point would be displayed like this:

Distances from Seattle to each city:
Dest. City     Distance  
-------------- --------
Miami              5.50
NewYork            4.50
LasVegas           3.00
Seattle            0.00
Columbus           3.50
Dallas             4.50
LosAngeles         3.00
Denver             2.00
SanFrancisco       2.00
Atlanta            4.50
Boston             5.00
StLouis            3.50
Chicago            3.00

(This example uses a HashMap - try using either both a HashMap and a TreeMap to track your distances.)

Explanation / Answer

Below java program helps to find the shortest path between two cities. Suppose that the city names are like A,B,C,D,E,F....... Z

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Vertex implements Comparable<Vertex>
{
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);
}

}

class Edge
{
public final Vertex target;
public final double weight;
public Edge(Vertex argTarget, double argWeight)
{ target = argTarget; weight = argWeight; }
}

public class Dijkstra
{
public static void computePaths(Vertex source)
{
source.minDistance = 0.;
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
vertexQueue.add(source);

while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();

  
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<Vertex> getShortestPathTo(Vertex target)
{
List<Vertex> path = new ArrayList<Vertex>();
for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
path.add(vertex);

Collections.reverse(path);
return path;
}

public static void main(String[] args)
{
// mark all the vertices
Vertex A = new Vertex("A");
Vertex B = new Vertex("B");
Vertex D = new Vertex("D");
Vertex F = new Vertex("F");
Vertex K = new Vertex("K");
Vertex J = new Vertex("J");
Vertex M = new Vertex("M");
Vertex O = new Vertex("O");
Vertex P = new Vertex("P");
Vertex R = new Vertex("R");
Vertex Z = new Vertex("Z");

// set the edges and weight
A.adjacencies = new Edge[]{ new Edge(M, 8) };
B.adjacencies = new Edge[]{ new Edge(D, 11) };
D.adjacencies = new Edge[]{ new Edge(B, 11) };
F.adjacencies = new Edge[]{ new Edge(K, 23) };
K.adjacencies = new Edge[]{ new Edge(O, 40) };
J.adjacencies = new Edge[]{ new Edge(K, 25) };
M.adjacencies = new Edge[]{ new Edge(R, 8) };
O.adjacencies = new Edge[]{ new Edge(K, 40) };
P.adjacencies = new Edge[]{ new Edge(Z, 18) };
R.adjacencies = new Edge[]{ new Edge(P, 15) };
Z.adjacencies = new Edge[]{ new Edge(P, 18) };

computePaths(A);
System.out.println("Distance to " + Z + ": " + Z.minDistance);
List<Vertex> path = getShortestPathTo(Z);
System.out.println("Path: " + path);
}
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.