implement Dijkstra\'s algorithm. import java.util.HashMap; import java.util.Link

ID: 656520 • Letter: I

Question

implement Dijkstra's algorithm.

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 {
       public String name;
       public LinkedList roads;

       // for pathing algorithms
       public float distance;
       public City previous;

       public City(String name) {
           this.name = name;
           this.roads = new LinkedList();

           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 {
       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 nodes;

// do not add more instance variables

   // constructor. You do not need to modify this.
   public City_Graph() {
       this.nodes = new HashMap();
   }

   /**
   * addCity.
   *
   * Add a City (node) to the graph
   *
   * @param name
   * the name of the city to add
   */
   public void addCity(String name) {
       // YOUR CODE HERE
   }

   /**
   * 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) {
       // 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 getPath(String a, String b) {
       // 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

implement Dijkstra's algorithm

import java.util.HashMap;
import java.util.LinkedList;

public class City_Graph {
   // City = node.
   class City implements Comparable {
       public String name;
       public LinkedList roads;

       // for pathing algorithms
       public float distance;
       public City previous;

       public City(String name) {
           this.name = name;
           this.roads = new LinkedList();

           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 {
       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 nodes

public City_Graph() {

City c = new City();

c.add( name);

}

public void addCity(String name) {

City c = new City();

c.add(name);

Road r = new Road();

r.add(start City , end City , Weight);

}

public void addRoad(String a, String b, float weight) {

this.startCity=a;

this.endCity=b;

this.Weight=weight;

Distance dis = new Distance();

}

public float distance(String a, String b) {

this.dis=float(a);

this .dis=float(b);

getPath path = new getPath();

}

public LinkedList getPath(String a1, String b1) {

this.path=a1;

this.path=b1;

}

Navigate

implement Dijkstra\'s algorithm by modifying addCity, addRoad, distance and getP

implement MLFQ using C++ please using linked list do not ask for user input will

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

implement Dijkstra\'s algorithm. import java.util.HashMap; import java.util.Link

Question

Explanation / Answer

Related Questions

Navigate