implement Dijkstra\'s algorithm by modifying addCity, addRoad, distance and getP
ID: 658030 • Letter: I
Question
implement Dijkstra's algorithm by modifying addCity, addRoad, distance and getPath only. thank you very much.
import java.util.HashMap;
import java.util.LinkedList;
public class City_Graph {
// City = node. You do not need to modify this class
class City implements Comparable<City> {
public String name;
public LinkedList<Road> roads;
// for pathing algorithms
public float distance;
public City previous;
public City(String name) {
this.name = name;
this.roads = new LinkedList<Road>();
distance = Float.MAX_VALUE;
previous = null;
}
@Override
public String toString() {
return this.name.toString();
}
@Override
public int compareTo(City o) {
return (int) (this.distance - o.distance);
}
}
// Road = weighted, directed connection between cities. You do not need
// to modify this class
class Road implements Comparable<Road> {
public City a;
public City b;
public float weight;
public Road(City a, City b, float weight) {
this.a = a;
this.b = b;
this.weight = weight;
}
@Override
public String toString() {
return this.a.toString() + " to " + this.b.toString() + " : "
+ this.weight;
}
@Override
public int compareTo(Road o) {
return (int) (this.weight - o.weight);
}
}
// the map of nodes in this graph
private HashMap<String, City> nodes;
// do not add more instance variables
// constructor. You do not need to modify this.
public City_Graph() {
this.nodes = new HashMap<String, City>();
}
/**
* addCity.
*
* Add a City (node) to the graph
*
* @param name
* the name of the cityport to add
*/
public void addCity(String name) {
// YOUR CODE HEREz
}
/**
* addRoad.
*
* Add a road (edge) to the graph
*
* @param a
* start City
* @param b
* end City
* @param weight
* the weight of the edge
*/
public void addRoad(String a, String b, float weight) {
// YOUR CODE HERE
}
/**
* distance
*
* Calculate the distance from City a to Road b using Dijkstra's
* Algorithm.
*
* @param a
* start city
* @param b
* end city
*/
public float distance(String a, String b) {
return 0;
// CODE HERE
}
/**
* getPath
*
* Return the path (in order) of roads to go from City a to City b.
* This must be the shortest path as determined by Dijkstra's algorithm.
*
* @param a
* start city
* @param b
* end city
*/
public LinkedList<Road> getPath(String a, String b) {
return null;
// CODE HERE
}
}
public class Tester
{
public static void main(String[] args)
{
City_Graph g = new City_Graph();
g.addCity("LA");
g.addCity("SF");
g.addCity("SJ");
g.addCity("a");
g.addCity("b");
g.addCity("c");
g.addRoad("LA", "SJ", 1.5f);
g.addRoad("LA", "SF", 1.75f);
g.addRoad("SJ", "a", 0.5f);
g.addRoad("SF", "b", 0.75f);
g.addRoad("SF", "LA", 1.75f);
g.addRoad("SF", "SJ", 0.5f);
g.addRoad("b", "c", 1.0f);
g.addRoad("SJ", "SF", 0.5f);
System.out.printf("Actual: %.2f%n", g.distance("LA", "SF"));
System.out.printf("Expected: 1.75%n");
System.out.printf("Actual: %s%n", g.getPath("LA", "SF"));
System.out.printf("Expected: [LA to SF : 1.75]%n");
System.out.printf("Actual: %.2f%n", g.distance("LA", "a"));
System.out.printf("Expected: 2.00%n");
System.out.printf("Actual: %s%n", g.getPath("LA", "a"));
System.out.printf("Expected: [LA to SJ : 1.5, SJ to a : 0.5]%n");
System.out.printf("Actual: %.2f%n", g.distance("LA", "c"));
System.out.printf("Expected: 3.50%n");
System.out.printf("Actual: %s%n", g.getPath("LA", "c"));
System.out.printf("Expected: [LA to SF : 1.75, SF to b : 0.75, b to c : 1.0]%n");
System.out.printf("Actual: %.2f%n", g.distance("SJ", "LA"));
System.out.printf("Expected: 2.25%n");
System.out.printf("Actual: %s%n", g.getPath("SJ", "LA"));
System.out.printf("Expected: [SJ to SF : 0.5, SF to LA : 1.75]%n");
}
}
Explanation / Answer
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;
public class City_Graph
{
class City implements Comparable<City>
{
public String name;
public LinkedList<Road> roads;
public float distance;
public City previous;
public City(String name)
{
this.name = name;
this.roads = new LinkedList<Road>();
distance = Float.MAX_VALUE;
previous = null;
}
@Override
public String toString()
{
return this.name.toString();
}
@Override
public int compareTo(City o)
{
return (int) (this.distance - o.distance);
}
}
class Road implements Comparable<Road>
{
public City a;
public City b;
public float weight;
public Road(City a, City b, float weight)
{
this.a = a;
this.b = b;
this.weight = weight;
}
@Override
public String toString()
{
return this.a.toString() + " to " + this.b.toString() + " : "
+ this.weight;
}
@Override
public int compareTo(Road o)
{
return (int) (this.weight - o.weight);
}
}
private HashMap<String, City> nodes;
public City_Graph()
{
this.nodes = new HashMap<String, City>();
}
addCity.
Add a City (node) to the graph
public void addCity(String name)
{
if(!nodes.containsKey(name))
nodes.put(name, new City(name));
}
public void addRoad(String a, String b, float weight)
{
City city1 = new City(a);
City city2 = new City(b);
Road road = new Road(city1, city2, weight);
if(!nodes.containsKey(a))
nodes.put(a, city1);
if(!nodes.containsKey(b))
nodes.put(b, city2);
nodes.get(a).roads.add(road);
}
public float distance(String a, String b)
{
float distanceThroughU = 0;
City city1 = new City(a);
City city2 = new City(b);
city1.distance = 0;
PriorityQueue<City> vertexQueue = new PriorityQueue<City>();
vertexQueue.add(city1);
while (!vertexQueue.isEmpty()) {
City u = vertexQueue.poll();
for (Road e : u.roads)
{
City v = e.b;
float weight = e.weight;
distanceThroughU = u.distance + weight;
if(distanceThroughU < v.distance)
{
vertexQueue.remove(v);
v.distance = distanceThroughU ;
v.previous = u;
vertexQueue.add(v);
}
}
}
return distanceThroughU;
}
public LinkedList<Road> getPath(String a, String b)
{
return null;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.