Dijkstra algorithm

Dijkstra algorithm is a graph search algorithm to find a shortest path to from the start node to the goal node, or from the start node to all nodes in the graph. It is commonly used in routing.

Run Review see Project * Alone

Dijkstra algorithm. You can set another node as goal with the right mouse click. Drag to connect the nodes. In the combo box, you can select other algorithms as well.

Dijkstra algorithm can work with the graph where edges have different "length" (the cost of traversing them), as long as this cost is not negative. While running, it finds the shortest path to all nodes in the graph but can be stopped as soon as the path to the goal node is found. If the cost can be negative, Bellman-Ford algorithm can be used instead.

The algorithm

The algorithm assigns the "distance value" to every node. This value is the distance (cost) to reach the node from the initial (starting) node. This value is of course zero for the initial node itself. At the start of the algorithm, it is set to be infinite for all other nodes in the graph. The algorithm also needs to remember the collection of already visited nodes. The "current node" is initially set to the initial node.

The can be implemented as following:

1. For current node, calculate the tentative distance for all its unvisited nodes. For example, if current node (A) has distance of 7, and an edge connecting it with another node has a traversing cost of 2, the distance to B through A will be 7+2=9. If some larger distance has been previously assigned to this node, overwrite the distance.
2. Mark the current node as visited. A visited node will not be checked ever again. The distance, assigned to this node, is now is final and minimal.
3. Set the unvisited node with the smallest distance (from the start node, considering all nodes in graph) as the next "current node" and continue from step 1.

The algorithms terminates when the goal node becomes the current node. If we need to find the distance till every node, the algorithm runs until there are no more unvisited nodes remaining in the graph. Unlike the Depth first search, the algorithm does not store directly the path itself - if this path is required, it must be separately recorded.

Differently from the Depth first search, the algorithm does not directly simulate "walking over the graph". The new current node in the next iteration of the loop need not be picked next to the current node; it can be picked anywhere in the graph. However node that already has some assigned tentative distance will have priority over completely unknown node for that the current tentative distance is infinite. This rule will force the search to concentrate closer to the start node. For some complex graph significant part of nodes may stay unexplored as they definitely cannot be on a shortest path between the start and goal node.

Depending from how well the used data structures are implemented, the algorithm can run in from till time, where V is the number of vertexes and E is the number of edges^[1].

Dijkstra algorithm can be viewed as a separate case of A* algorithm with zero heuristic function.

References

1. ¹ Dijkstra algorithm page on Wikipedia.