Path finder algorithm java update#
We would then call the method that would update the weight of all vertices adjacent to the vertex in this node, which will perform the “relaxation” process in the dijkstra algorithm. When the looping portion of the dijkstra algorithm begins, we would call deleteMin and get the node with the smallest weight and store it in an ArrayList of known vertices which represented the shortest path. At this phase of the design, we were going to initialize all vertices on the graph with DijkstraNodes with a default weight of double POSITIVE_INFINITY and insert them into the heap at the beginning of the program, along with the origin vertex with weight 0 whose DijkstraNode would naturally be at the very top of the minheap. This data structure contained a mapping between a Vertex object and the index location of the DijkstraNode that contains this vertex in the heap. One of the early ideas that we implemented is the creation of another data structure, a TreeMap named VertexLocation. The DijkstraNode have the ability to store vertex information as part of its data, but there was no way to go the other direction and obtain a vertex’s corresponding DijkstraNode in order to change its properties in the heap. This is where we encountered the first major problem in our design. But once we get these adjacent vertices, where do we go next? We know that if we have a vertex, we can all vertices adjacent to this vertex by getting a list of all edges that are incident to this vertex and finding the vertex at the opposite end of this edge. Next, we were tasked in designing a workable model that will closely follow the pencil and paper implementation of the dijkstra algorithm commenly depicted in textbooks.
We already have vertices that we need to store into the heap by weight, but since we cannot modify the Vertex class we need to create a new data structure, named DijkstraNode, to store a vertex, it’s weight, its location in the heap, as well as a path pointer to a vertex which will come useful when we want to find the shortest path.
Path finder algorithm java code#
We use a pre-existing BinaryHeap class to do this and make a few minor modifications to the code so that it supports some of the properties that are unique to Dijkstra. The first major design element that we implemented is the structures that will create a functioning binary heap. We designed the Dijkstra class that we create to work with these classes. The basic structure of this graph is represented by the Vertex, Edge, and SimpleGraph class files.
A basic Java shortest path finder using Dijkstra's algorithm.Īuthors: Yong Yu Wang and Patrick Colowick-Harbour
0 kommentar(er)
