The Dijkstra's Algorithm (shortest route) finds the shortest distance and path from a source to all destination in a directed graph which is defined by a set of vertexes (V) and a collection of edges. I found the easiest way to understand how Dijkstra's algorithm works is to take a look at this visual explanation below: The ApproachInitially, set the distance from the source to each destination node to a very high value. These nodes with a very high initial value are not in settled nor in unsettled set. Dijkstra partitions nodes into two distinct sets - unsettled (unsolved) and settled. Nodes in unsettled set are those nodes still must be evaluated for a shortest path from the source. Nodes in settled set are those nodes that have their shortest distance from the sources found already. There are some nodes with a very high initial value are not in the settled set nor in the unsettled set to begin with. Nodes are gradually added to the unsettled set first before being moved in the settled set. To find the shortest distance, Dijkstra's algorithm selects a node from unsettled set, recalculate the distance from source to all its adjacent nodes (neighbors), then put the selected node to the settled set, and newly found adjacent nodes to the unsettled set. The selections is based on the least distance from the source to the unsettled node. This selection process is the findMinimalDistances(node) as seen below in the sample code. The selection process goes on until there's no node left in the unsettled set. Thought ProcessBefore we start, initialize the distance from the source to each destination node to a very high value. First, put only the source node into the unsettled set. Then, go through iterations. In each iteration, select the node with the lowest distance from the source from the unsettled set, put it into the settled set. Repeat until the unsettled set is empty. In each iteration, the algorithm selects one node with the lowest distance from the source out from the unsettled set. It also reads all edges which are outgoing from the selected node and evaluates each destination node in these edges and add these adjacent nodes to the unsettled set. Check if the known distance from the source to this destination node can be reduced if the selected edge is used. If this can be done, then the shortest distance (from the source to each destination) is updated and the node is added to the nodes which need evaluation. Code SnippetsModel A simple Vertex class with its hashCode() and equals() overridden. Remember, if a class overrides equals(), most likely, you must override hashCode() as well. public class Vertex{ A simple Edge class contains source vertex, destination vertex, uni-directional weight, with some getter, and setter functions: public class Edge{ Graph = {Vertex, Edge}: public class Graph{ Dijkstra's Algorithm Implementation Dijkstra's algorithm deals with a graph, so we choose to have the constructor to take in a Graph. Internally, the Dijkstra's algorithm class contains nodes and edges of the graph, plus the intermediate data structures (settled nodes, unsettled nodes, predecessors, and distance) to support the algorithm. Among them, the 'predecessors' Map is to trace the predecessor of a given node for the shortest path from the source, and the 'distance' Map is to hold the min distance going from the source node to any given vertex. public class DijkstraAlgorithm { At its core, execute(Vertex) is the main function that actually perform the Dijkstra's algorithm. At the end, the 'distance' Map will have the shortest distance from the given source vertex to all other vertex. public void execute(Vertex source) { [1] In Dijkstra's algorithm, this Map holds temporary distance from source vertex to any other given vertex. [2] This Map holds temporary predecessor of a given Vertex. A predecessor is a Vertex in a shortest path found so far before reaching a given Vertex. To look up a predecessor of a vertex V, just do predecessors.get(V). [3] Return a vertex among all unsettled nodes with the least distance from the source. [4] Given a node, go through its adjacent nodes. Recalculate the shortest distance held in 'distance' Map where temporary distance from source is held. Then add all adjacent node into unsettled set. The rest are helper functions called and used from execute(Vertex): // Given a node, go through its adjacent nodes. Recalculate the shortest references
0 Comments
Leave a Reply. |
Categories
All
Archives
May 2020
|