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

Question

implement Dijkstra's algorithm by modifying addCity, addRoad, distance and getPath only. thanks.

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 DijkstraAlgorithmSet { private int distances[]; private Set settled; private Set unsettled; private int number_of_nodes; private int adjacencyMatrix[][]; public DijkstraAlgorithmSet(int number_of_nodes) { this.number_of_nodes = number_of_nodes; distances = new int[number_of_nodes + 1]; settled = new HashSet(); unsettled = new HashSet(); adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1]; }

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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