Original Code, Screenshot of Zybooks, and Powerpoint of Zybooks steps (start at pg. 13) included in attachments!
"For this group assignment, use this list of flight costs (
Flights.txt
--- attached) to create a graph of the U.S. and determine the shortest path to each city from Terminal A (Miami).
You will notice that the example code uses a slightly different methodology than Zybooks (screenshot attached). Update the code to perform the algorithm in the same way as Zybooks."
1. You shouldn't need to change too much code. Change the dijkstra
algorithm so that the "queue" of nodes behaves the same as Zybooks. It is implemented differently in the example code.
2. You don't want to use a real queue. Dijkstra's algorithm relies on
finding the lowest distance node in the graph to "visit" next so a queue data structure isn't needed.
import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Map.Entry; import java.util.Set; class Graph { private Set
nodes = new HashSet<>(); public void addNode(Node node) { nodes.add(node); } public Set getNodes() { return nodes; } } class Node { private String name; private List shortestPath = new LinkedList<>(); private Integer distance = Integer.MAX_VALUE; Map adjacentNodes = new HashMap<>(); public void addDestination(Node destination, int distance) { adjacentNodes.put(destination, distance); } public Node(String name) { this.name = name; } public void setDistance(int dist) { distance = dist; } public int getDistance() { return distance; } public Map getAdjacentNodes() { return adjacentNodes; } public List getShortestPath() { return shortestPath; } public void setShortestPath(List newshortestpath) { shortestPath = newshortestpath; } @Override public String toString() { return name; } } class Dijkstra { public static Graph calculateShortestPathFromSource(Graph graph, Node source) { source.setDistance(Integer.MAX_VALUE); Set settledNodes = new HashSet<>(); Set unsettledNodes = new HashSet<>(); unsettledNodes.add(source); while (unsettledNodes.size() != 0) { Node currentNode = getLowestDistanceNode(unsettledNodes); unsettledNodes.remove(currentNode); for (Entry adjacencyPair : currentNode.getAdjacentNodes().entrySet()) { Node adjacentNode = adjacencyPair.getKey(); Integer edgeWeight = adjacencyPair.getValue(); if (!settledNodes.contains(adjacentNode)) { CalculateMinimumDistance(adjacentNode, edgeWeight, currentNode); unsettledNodes.add(adjacentNode); } } settledNodes.add(currentNode); } return graph; } private static Node getLowestDistanceNode(Set unsettledNodes) { Node lowestDistanceNode = null; int lowestDistance = Integer.MAX_VALUE; for (Node node : unsettledNodes) { int nodeDistance = node.getDistance(); if (nodeDistance < lowestdistance)="" {="" lowestdistance="nodeDistance;" lowestdistancenode="node;" }="" }="" return="" lowestdistancenode;="" }="" private="" static="" void="" calculateminimumdistance(node="" evaluationnode,="" integer="" edgeweigh,="" node="" sourcenode)="" {="" integer="" sourcedistance="sourceNode.getDistance();" if="" (sourcedistance="" +="" edgeweigh="">< evaluationnode.getdistance())="" {="" evaluationnode.setdistance(sourcedistance="" +="" edgeweigh);=""> shortestPath = new LinkedList<>(sourceNode.getShortestPath()); shortestPath.add(sourceNode); evaluationNode.setShortestPath(shortestPath); } } } public class Assignment11 { public static void main(String args[]) { Node nodeA = new Node("A"); Node nodeB = new Node("B"); Node nodeC = new Node("C"); Node nodeD = new Node("D"); Node nodeE = new Node("E"); Node nodeF = new Node("F"); Node nodeG = new Node("G"); Node nodeH = new Node("H"); nodeH.addDestination(nodeF, 218); nodeH.addDestination(nodeD, 65); nodeH.addDestination(nodeG, 78); nodeG.addDestination(nodeA, 278); nodeG.addDestination(nodeF, 315); nodeG.addDestination(nodeH, 218); nodeD.addDestination(nodeE, 280); nodeD.addDestination(nodeC, 250); nodeD.addDestination(nodeH, 65); nodeC.addDestination(nodeD, 250); nodeC.addDestination(nodeB, 168); nodeA.addDestination(nodeG, 278); nodeA.addDestination(nodeH, 115); nodeA.addDestination(nodeB, 155); nodeB.addDestination(nodeA, 155); nodeB.addDestination(nodeC, 168); nodeF.addDestination(nodeE, 145); nodeF.addDestination(nodeH, 218); nodeF.addDestination(nodeG, 315); nodeE.addDestination(nodeF, 145); nodeE.addDestination(nodeD, 280); Graph graph = new Graph(); graph.addNode(nodeA); graph.addNode(nodeB); graph.addNode(nodeC); graph.addNode(nodeD); graph.addNode(nodeE); graph.addNode(nodeF); graph.addNode(nodeG); graph.addNode(nodeH); graph = Dijkstra.calculateShortestPathFromSource(graph, nodeA); for (Node node : graph.getNodes()) System.out.println(node.toString() + node.getDistance() + node.getShortestPath()); } } PowerPoint Presentation Quiz from Last Week Assignment from Last Week Lecture 10 Graphs (Continued) Searching a Graph There are a few ways to traverse a graph The two we’ll talk about are: Breadth-first search (BFS) Depth-first search (DFS) Breadth-first Search Traversal algorithm that visits a starting vertex, then all vertices of distance 1 It then visits all vertices of distance 2 and repeats outward without revisiting a vertex Accomplishes this by using a “queue” Breadth-first Search The starting vertex is added to the queue The algorithm pops a vertex from the queue and visits the popped vertex Then, that vertex’s adjacent vertices are pushed into the queue (if they haven’t already been discovered) This process repeats Breadth-first Search The vertices in the queue are called the frontier These have been “discovered” but not yet visited A vertex only needs to be visited once so an already-discovered vertex is not pushed to the queue again A visit may mean to print the vertex, compare it to a value, etc. Depth-first Search A depth-first search (DFS) is a traversal that visits a starting vertex, then visits every vertex along each available path until it reaches the end. A stack is used for this algorithm Depth-first Search The starting vertex is pushed onto a stack The algorithm pops a vertex from the top of the stack If the vertex has not already been visited, the algorithm visits the vertex and pushes the adjacent vertices to the stack Depth-first Search A depth-first search can also be accomplished through recursion using the call stack The algorithm is first called with the starting vertex Visit the vertex and then perform a recursive DFS call for each adjacent vertex Conceptual Example https://www.youtube.com/watch?v=bIA8HEEUxZI Finding the Shortest Path Finding the shortest path between vertices in a graph has many applications Find the shortest traffic route between two intersections Find the fastest travel time (using travel time as edge weights) Dijkstra’s Shortest Path Algorithm Created by Edsger Dijkstra Determines the shortest path from a start vertex to each vertex in a graph Dijkstra’s Algorithm Terminology A vertex’s distance is the shortest path to it from the start vertex A vertex’s predecessor pointer points to the previous vertex along the shortest path from the start vertex When referring to this algorithm, we’ll use the term ‘queue’ to describe the collection of vertices not yet visited It is NOT the same as the Queue data structure we have previously discussed Dijkstra’s Algorithm Initial Actions: Initialize all vertices’ distances to infinity Initialize all vertices’ predecessors to zero Push all vertices to a queue of unvisited vertices Assign the start vertex’s distance as zero Dijkstra’s Algorithm Steps (continued): The vertex with the shortest distance is popped from the queue For each adjacent vertex, compute the distance of the path from the start vertex to the current vertex and continue on to the adjacent vertex If that path’s distance is shorter than the adjacent vertex’s current distance, a shorter path has been found Dijkstra’s Algorithm Steps (Continued): The adjacent vertex’s current distance is updated to the newly found shortest path The adjacent vertex’s predecessor pointer is pointed to the current vertex Dijkstra’s Algorithm After running the algorithm, the shortest path from the start vertex to a destination vertex can be determined using the vertices’ predecessor pointers If the destination’s predecessor pointer is not zero, the shortest path is followed in reverse through the predecessor pointers until reaching the start vertex Else, a path from the destination to start does not exist Dijkstra’s Algorithm Dijkstra Performance If the unvisited vertex queue is implemented using a list The algorithm runtime is O(V2) The outer loop executes V times to visit all vertices Each popping operation requires searching all vertices in the list O(V) Dijkstra Performance Implementing the queue using a heap data structure reduces the runtime to O(E + Vlog(V)) This algorithm can be used for unweighted graphs and weighted graphs with non-negative edge weights Results are unreliable with negative edge weights Break Bellman-Ford’s Shortest Path This algorithm performs V-1 main iterations, visiting all vertices in the graph during each iteration Each time a vertex is visited, the algorithm follows all edges to adjacent vertices Bellman-Ford’s Shortest Path This algorithm does not require a specific order for visiting vertices during each main iteration So after each iteration, a vertex’s current distance and predecessor may not yet be the shortest path from the start vertex Bellman-Ford’s Shortest Path The shortest path may propagate to only one vertex each iteration Requires V-1 iterations to propagate from the start vertex to all other vertices Bellman-Ford Example Bellman-Ford Performance The runtime is O(VE) E is total of edges There are V-1 outer loop iterations In each outer loop execution, the algorithm visits each vertex and follows the subset of edges to adjacent vertices Bellman-Ford Negative Edges Supports graphs with negative edge weights As long as no negative edge weight cycle exists The algorithm checks for negative edge weight cycles after visiting all vertices V-1 times Bellman-Ford Negative Edges How does it determine if a negative cycle exists? After the algorithm has visited all vertices V-1 times, we should be guaranteed to have determined the shortest paths for all vertices If we visit all the vertices one more time and any of their distances decrease, then a negative cycle must exist Dijkstra vs. Bellman-Ford Dijkstra is faster but doesn’t work with negative edge weights Faster because it visits each vertex only once and can use a heap for the vertex queue to increase performance Bellman-Ford is a slower brute force methodology but it works with negative edge weights It can also detect negative edge weight cycles Fun Semi-interactive Example Graph Breadth-first Search Quiz this Week Topic: Graph Searching and Shortest Path Assignment this Week Zybooks Sections for Today 5.4, 5.5, 5.8, 5.9