You are to implement Dijkstra\'s algorithm. Which data structures and algorithms

Question

You are to implement Dijkstra's algorithm. Which data structures and algorithms you would use and why those rather than some alternative. Be sure to specify the contents of any required record types.

Dijkstra's Single-source Shortest Path Algorithm

Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra's algorithm will assign some initial distance values and will try to improve them step by step.

(a) Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.

(b) Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node.

(c) For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded distance, then overwrite that distance. Even though a neighbor has been examined, it is not marked as visited at this time, and it remains in the unvisited set.

(d) When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again; its distance recorded now is nal and minimal.

(e) If the unvisited set is empty, then stop. The algorithm has nished.

(f) Set the unvisited node marked with the smallest tentative distance as the next "current node" and go back to step 3.

Explanation / Answer

Dijkstra's Algorithm is a graph-search algorithm that finds the shortest path between two Vertices on a weighted Graph. For Dijkstra's algorithm, we assume that all distances are positive. So how exactly does this algorithm work? Basically, we initialize all the distances to infinity, except for the root Vertex which is initialized to 0. We then traverse the Graph from the starting point towards the end point. When we hit a Node, we evaluate the cumulative distance to that Node, which means the distance recorded at the previous Node plus to the distance to the current Node. So if we have A-->B weighted at 5 and B-->C weighted at C, B would record the distance 5, and C would record the distance 8. The reason we initialize to infinity is that the first time we hit that Node, everything will be less than infinity so the first distance will be stored at that Node. For the purpose of this tutorial, I've set up a class to handle evaluating Dijkstra's algorithm using my Graph implementation from my Graphs Tutorial. I used Integer.MAX_VALUE as my infinity marker. 01 import java.util.*; 02 03 /** 04 * A utility class to implement Dijkstra's algorithm 05 * @param E: The type to store in the Graph 06 * */ 07 public class Dijkstra { 08 09 //the Graph to traverse 10 private Graph graph; 11 12 //the PriorityQueue for the heap-based sort 13 private PriorityQueue heap; 14 15 /** 16 * @param graph: The Graph to traverse 17 * 18 * The constructor initializes each Node's 19 * distance to Integer.MAX_VALUE, as the infinity value. 20 * When the weights are compared, they are initially compared 21 * to MAX_VALUE, which they will be less than. 22 * */ 23 public Dijkstra(Graph graph){ 24 this.graph = graph; 25 resetGraph(); 26 heap = new PriorityQueue(25, new Comparator(){ 27 public int compare(Connector one, Connector two){ 28 return (one.getDistance() + one.getOne().getDistance()) - 29 (two.getDistance() + two.getOne().getDistance()); 30 } 31 }); 32 33 } 34 35 //initializes the Graph Nodes to infinity 36 public void resetGraph(){ 37 for(int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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