/////////////////////////////////////////// /// /// File: DijkstraGraph.java /// Author: Evan Gaul /// Email: eagaul@wisc.edu /// Date: 11/12/25 /// Assignment: P210.ShortestPath /// Course: CS400 Lec004 Fall 2025 /// Professor: Ashley Samuelson /// /////////////////////////////////////////// /// /// Assistance: None /// /////////////////////////////////////////// import java.util.PriorityQueue; import java.util.List; import java.util.LinkedList; import java.util.NoSuchElementException; import org.junit.jupiter.api.Test; 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() { super(new PlaceholderMap<>()); } /** * 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 of SearchNodes, ordered by cost PriorityQueue pq = new PriorityQueue<>(); // Use PlaceholderMap as a visited set PlaceholderMap visited = new PlaceholderMap<>(); pq.add(new SearchNode(start));// Add starting node to priority queue while (!pq.isEmpty()) { SearchNode current = pq.poll(); // Skip if already visited if (visited.containsKey(current.node)) continue; // Mark as visited visited.put(current.node, current.node); // If we've reached the target node, return it if (current.node.equals(end)) return current; // Explore all edges leaving current node for (Edge edge : current.node.edgesLeaving) { Node neighbor = edge.succ; if (!visited.containsKey(neighbor)) { pq.add(new SearchNode(current, edge)); } } } // If we exit without finding the end node throw new NoSuchElementException("No path exists between the given 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); SearchNode result = computeShortestPath(startNode, endNode); // Build the path list from end to start, then reverse LinkedList path = new LinkedList<>(); for (SearchNode cur = result; cur != null; cur = cur.pred) path.addFirst(cur.node.data); 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) { Node startNode = nodes.get(start); Node endNode = nodes.get(end); SearchNode result = computeShortestPath(startNode, endNode); return result.cost; } /////////////////////////////////////////////////////////////////////////////////////////////////// /// JUNIT TESTS! /////////////////////////////////////////////////////////////////////////////////////////////////// /** * Tests the basic example graph from lecture * I used the example used in TopHat and used A->F to test */ @Test public void testLectureExample() { DijkstraGraph g = new DijkstraGraph<>(); g.insertNode("A"); g.insertNode("B"); g.insertNode("C"); g.insertNode("D"); g.insertNode("E"); g.insertNode("F"); g.insertEdge("A", "B", 3.0); g.insertEdge("B", "D", 2.0); g.insertEdge("A", "E", 6.0); g.insertEdge("D", "E", 2.0); g.insertEdge("B", "E", 5.0); g.insertEdge("B", "C", 5.0); g.insertEdge("E", "C", 7.0); g.insertEdge("E", "F", 3.0); g.insertEdge("F", "C", 5.0); List path = g.shortestPathData("A", "F"); // Should be A,E,F double cost = g.shortestPathCost("A","F"); // Should be 9.0 assertEquals(9.0, cost); assertEquals( java.util.List.of("A", "E", "F"), path); } /** * Tests a graph where one node is disconnected, no path exists */ @Test public void testNoPathExists() { DijkstraGraph g = new DijkstraGraph<>(); g.insertNode("A"); g.insertNode("B"); g.insertNode("C"); g.insertEdge("A", "B", 1.0); // C is disconnected assertThrows(NoSuchElementException.class, () -> {g.shortestPathCost("A", "C");}); // error should be thrown } /** * Tests when start or end node does not exist */ @Test public void testNodeDoesNotExist() { DijkstraGraph g = new DijkstraGraph<>(); g.insertNode("A"); g.insertNode("B"); g.insertEdge("A", "B", 2.0); // errors should be thrown, Z is not in the graph assertThrows(NoSuchElementException.class, () -> {g.shortestPathCost("A", "Z");}); assertThrows(NoSuchElementException.class, () -> {g.shortestPathData("Z", "B");}); } }