import java.util.PriorityQueue; import org.junit.jupiter.api.Test; import java.util.List; import java.util.LinkedList; import java.util.NoSuchElementException; import static org.junit.jupiter.api.Assertions.*; /** * This class extends the BaseGraph data structure with additional methods for * computing the total cost and list of node data along the shortest path * connecting a provided starting to ending nodes. This class makes use of * Dijkstra's shortest path algorithm. */ public class DijkstraGraph extends BaseGraph implements GraphADT { /** * While searching for the shortest path between two nodes, a SearchNode * contains data about one specific path between the start node and another * node in the graph. The final node in this path is stored in its node * field. The total cost of this path is stored in its cost field. And the * predecessor SearchNode within this path is referenced by the predecessor * field (this field is null within the SearchNode containing the starting * node in its node field). * * SearchNodes are Comparable and are sorted by cost so that the lowest cost * SearchNode has the highest priority within a java.util.PriorityQueue. */ protected class SearchNode implements Comparable { public Node node; public double cost; public SearchNode pred; public SearchNode(Node startNode) { this.node = startNode; this.cost = 0; this.pred = null; } public SearchNode(SearchNode pred, Edge newEdge) { this.node = newEdge.succ; this.cost = pred.cost + newEdge.data.doubleValue(); this.pred = pred; } public int compareTo(SearchNode other) { if (cost > other.cost) return +1; if (cost < other.cost) return -1; return 0; } } /** * Constructor that sets the map that the graph uses. */ public DijkstraGraph() { // hashtable instead of placeholder super(new HashtableMap<>()); } /** * This helper method creates a network of SearchNodes while computing the * shortest path between the provided start and end locations. The * SearchNode that is returned by this method represents the end of the * shortest path that is found: it's cost is the cost of that shortest path, * and the nodes linked together through predecessor references represent * all of the nodes along that shortest path (ordered from end to start). * * @param start the starting node for the path * @param end the destination node for the path * @return SearchNode for the final end node within the shortest path * @throws NoSuchElementException when no path from start to end is found * or when either start or end data do not * correspond to a graph node */ protected SearchNode computeShortestPath(Node start, Node end) { // Priority queue for search nodes and map for visited nodes PriorityQueue pq = new PriorityQueue<>(); PlaceholderMap visited = new PlaceholderMap<>(); // add starting node pq.add(new SearchNode(start)); // Dijkstra loop while (pq.isEmpty() == false) { // set curr to smallest cost node SearchNode curr = pq.poll(); // skip if final if (visited.containsKey(curr.node)) continue; // mark node as visited visited.put(curr.node, curr.node); // return final if reached destination if (curr.node == end) return curr; // explore each edge from curr for (Edge edge : curr.node.edgesLeaving) { if (!visited.containsKey(edge.succ)) { // create new node for extended path SearchNode next = new SearchNode(curr, edge); pq.add(next); } } } // no path exists throw new NoSuchElementException("No path exists between provided nodes."); } /** * Returns the list of data values from nodes along the shortest path * from the node with the provided start value through the node with the * provided end value. This list of data values starts with the start * value, ends with the end value, and contains intermediary values in the * order they are encountered while traversing this shortest path. This * method uses Dijkstra's shortest path algorithm to find this solution. * * @param start the data item in the starting node for the path * @param end the data item in the destination node for the path * @return list of data item from nodes along this shortest path */ public List shortestPathData(NodeType start, NodeType end) { Node startNode = nodes.get(start); Node endNode = nodes.get(end); // compute the final search node (contains cost and predecessor chain) SearchNode finalNode = computeShortestPath(startNode, endNode); // reconstruct path LinkedList path = new LinkedList<>(); SearchNode curr = finalNode; while (curr != null) { path.addFirst(curr.node.data); curr = curr.pred; } return path; } /** * Returns the cost of the path (sum over edge weights) of the shortest * path from the node containing the start data to the node containing the * end data. This method uses Dijkstra's shortest path algorithm to find * this solution. * * @param start the data item in the starting node for the path * @param end the data item in the destination node for the path * @throws NoSuchElementException if either the start of the end node cannot be found, or there is no path from the start to the end node * @return the cost of the shortest path between these nodes */ public double shortestPathCost(NodeType start, NodeType end) { // throw NSEE if start and/or end nodes don't exist if (!nodes.containsKey(start)) { throw new NoSuchElementException("Start node " + start + " not in the graph."); } if (!nodes.containsKey(end)) { throw new NoSuchElementException("End node " + end + " not in the graph."); } Node startNode = nodes.get(start); Node endNode = nodes.get(end); // get final node for shortest path SearchNode finalNode = computeShortestPath(startNode, endNode); // return total path cost return finalNode.cost; } /** * Test number 1: Lecture example shortest path A to F */ @Test public void testLectureExample() { DijkstraGraph graph = new DijkstraGraph<>(); String[] nodes = {"A", "B", "C", "D", "E", "F", "G", "H"}; // insert nodes for (String node:nodes) graph.insertNode(node); // Lecture edges graph.insertEdge("A", "B", 4.0); graph.insertEdge("A", "C", 15.0); graph.insertEdge("A", "E", 2.0); graph.insertEdge("B", "C", 10.0); graph.insertEdge("B", "F", 1.0); graph.insertEdge("E", "F", 5.0); graph.insertEdge("F", "C", 3.0); graph.insertEdge("F", "G", 0.0); graph.insertEdge("G", "F", 2.0); graph.insertEdge("G", "H", 4.0); graph.insertEdge("D", "H", 4.0); // find cost double cost = graph.shortestPathCost("A", "F"); assertEquals(5.0, cost, 0.001, "Shortest path A to F should be 5"); // assert shortest path List path = graph.shortestPathData("A", "F"); assertArrayEquals(new String[]{"A", "B", "F"}, path.toArray(), "Shortest path A to F should be [A, B, F]"); } /** * Test number 2: Different start and end nodes B to H test */ @Test public void testPathBFH() { DijkstraGraph graph = new DijkstraGraph<>(); String[] nodes = {"A", "B", "C", "D", "E", "F", "G", "H"}; //insert nodes for (String node:nodes) graph.insertNode(node); graph.insertEdge("A", "B", 4.0); graph.insertEdge("A", "C", 15.0); graph.insertEdge("A", "E", 2.0); graph.insertEdge("B", "C", 10.0); graph.insertEdge("B", "F", 1.0); graph.insertEdge("E", "F", 5.0); graph.insertEdge("F", "C", 3.0); graph.insertEdge("F", "G", 0.0); graph.insertEdge("G", "F", 2.0); graph.insertEdge("G", "H", 4.0); graph.insertEdge("D", "H", 4.0); //find cost and assertions on cost, start to end double cost = graph.shortestPathCost("B", "H"); assertEquals(5.0, cost, 0.001, "Shortest path B to H should be 5"); List path = graph.shortestPathData("B", "H"); assertArrayEquals(new String[]{"B", "F", "G", "H"}, path.toArray(), "Shortest path B to H should be [B, F, G, H]"); } /** * Test number 3: No path, throw NSEE */ @Test public void testNoPathOrMissingNode() { DijkstraGraph graph = new DijkstraGraph<>(); // insert nodes graph.insertNode("A"); graph.insertNode("B"); graph.insertEdge("A", "B", 3.0); // No path B to A + lambda expression assertThrows(NoSuchElementException.class, () -> graph.shortestPathCost("B", "A")); // Start node missing assertThrows(NoSuchElementException.class, () -> graph.shortestPathData("X", "B")); // Last node missing assertThrows(NoSuchElementException.class, () -> graph.shortestPathCost("A", "Y")); } }