Create a transportation logistics system that allows a user to enter a city to c

Question

Create a transportation logistics system that allows a user to enter a city to city connection and their prices. Your system should allow a user to enter two cities and should return the shortest path and the cheapest path between the two cities. Use a directed weighted graph. You may use Dijkstra

Explanation / Answer

//City.java /*City is equivalent to Vertex in Graph */ public class City { final private String id; final private String name; public City(String id, String name) { this.id = id; this.name = name; } public String getId() { return id; } public String getName() { return name; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((id == null) ? 0 : id.hashCode()); return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; City other = (City) obj; if (id == null) { if (other.id != null) return false; } else if (!id.equals(other.id)) return false; return true; } @Override public String toString() { return name; } } //Path.java /* Path is equivalent to Edge in Graph */ public class Path { private final String id; private final City source; private final City destination; private final int weight; public Path(String id, City source, City destination, int weight) { this.id = id; this.source = source; this.destination = destination; this.weight = weight; } public String getId() { return id; } public City getDestination() { return destination; } public City getSource() { return source; } public int getWeight() { return weight; } @Override public String toString() { return source + " " + destination; } } //CityNetwork.java /* CityNetwork is equivalent to Graph that shows the connections and Cities */ import java.util.ArrayList; public class CityNetwork { private final ArrayList Cities; private final ArrayList Paths; public CityNetwork(ArrayList Cityes, ArrayList Paths) { this.Cities = Cityes; this.Paths = Paths; } public ArrayList getCityes() { return Cities; } public ArrayList getPaths() { return Paths; } } //DijkstraAlgorithm.java /* Dijkstr aAlgorithm implementation */ import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.Map; import java.util.Set; public class DijkstraAlgorithm { private final ArrayList nodes; private final ArrayList Paths; private Set settledNodes; private Set unSettledNodes; private Map predecessors; private Map distance; public DijkstraAlgorithm(CityNetwork graph) { // Create a copy of the array so that we can operate on this array this.nodes = new ArrayList(graph.getCityes()); this.Paths = new ArrayList(graph.getPaths()); } public void execute(City source) { settledNodes = new HashSet(); unSettledNodes = new HashSet(); distance = new HashMap(); predecessors = new HashMap(); distance.put(source, 0); unSettledNodes.add(source); while (unSettledNodes.size() > 0) { City node = getMinimum(unSettledNodes); settledNodes.add(node); unSettledNodes.remove(node); findMinimalDistances(node); } } private void findMinimalDistances(City node) { ArrayList adjacentNodes = getNeighbors(node); for (City target : adjacentNodes) { if (getShortestDistance(target) > getShortestDistance(node) + getDistance(node, target)) { distance.put(target, getShortestDistance(node) + getDistance(node, target)); predecessors.put(target, node); unSettledNodes.add(target); } } } private int getDistance(City node, City target) { for (Path Path : Paths) { if (Path.getSource().equals(node) && Path.getDestination().equals(target)) { return Path.getWeight(); } } throw new RuntimeException("Should not happen"); } private ArrayList getNeighbors(City node) { ArrayList neighbors = new ArrayList(); for (Path Path : Paths) { if (Path.getSource().equals(node) && !isSettled(Path.getDestination())) { neighbors.add(Path.getDestination()); } } return neighbors; } private City getMinimum(Set Cityes) { City minimum = null; for (City City : Cityes) { if (minimum == null) { minimum = City; } else { if (getShortestDistance(City) = 3) { int fromCityIndex = getIndexByCityName(tmpString[0]); int toCityIndex = getIndexByCityName(tmpString[1]); addLane("Path_"+ nPathCount++, fromCityIndex, toCityIndex, Integer.parseInt(tmpString[2])); } else { System.out.println("Invalid Input."); continue; } System.out.println("Do you want to add one more Path? :"); s = ReadInput(); if(s.toUpperCase().equals("N")) break; } // Lets check from location Loc_1 to Loc_10 CityNetwork graph = new CityNetwork(nodes, Paths); DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(graph); System.out.println("Enter Source and Destination cities to find out Shortest Path :"); s = ReadInput(); String[] inputTest = s.split(","); if(inputTest.length>=2) { int nSrcCityIndex = getIndexByCityName(inputTest[0]); int nDestCityIndex = getIndexByCityName(inputTest[1]); //This method takes the Source or From City as input dijkstra.execute(nodes.get(nSrcCityIndex)); //This method takes Target City as input and returns the shortest path //from the source city LinkedList path = dijkstra.getPath(nodes.get(nDestCityIndex)); //Prinitng the shortest path System.out.println(" The Shortest Path is : "); for (City City : path) { System.out.println(City); } } } private static int getIndexByCityName(String strName) { for(int i = 0; i from city, to city, price Please enter path#1 : Sheraton,Livingston,6 Do you want to add one more Path? : y Please enter path#2 : Sheraton,Student Center,5 Do you want to add one more Path? : y Please enter path#3 : Sheraton,Construction1,6 Do you want to add one more Path? : y Please enter path#4 : Construction1,Construction2,6 Do you want to add one more Path? : y Please enter path#5 : Construction1,Bridge,2 Do you want to add one more Path? : y Please enter path#6 : Student Center,Construction2,5 Do you want to add one more Path? : y Please enter path#7 : Livingston,Construction2,9 Do you want to add one more Path? : y Please enter path#8 : Livingston,Construction1,3 Do you want to add one more Path? : y Please enter path#9 : Livingston,Bridge,8 Do you want to add one more Path? : y Please enter path#10 : Construction2,DIMACS,4 Do you want to add one more Path? : y Please enter path#11 : Bridge,DIMACS,8 Do you want to add one more Path? : n Enter Source and Destination cities to find out Shortest Path : Sheraton,DIMACS The Shortest Path is : Sheraton Student Center Construction2 DIMACS BUILD SUCCESSFUL

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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