Pathfinding has gained prominence in the early 1950's in the context of routing; that is, finding shortest directions between two or more nodes. In 1956, the Dutch software engineer Edsger Wybe Dijkstra created the best-known of these algorithms : Dijkstra.

Dijkstra’s algorithm finds the shortest path from a root node to every other node (until the target is reached). Dijkstra is one of the most useful graph algorithms; furthermore, it can easily be modified to solve many different problems.

Traversal algorithms such as breadth-first-search and depth-first-search explore all possibilities : they iterate over all possible paths until they reach the target. However, it may not be necessary to examine all possible paths; Dijkstra’s algorithm eliminates useless traversal using heuristics to find the optimal paths.

### Some applications

• Widely used in Network routing protocols.
• In digital mapping services such as Google Maps.
• In Biology by finding the network model in spreading of infectious diseases.
• In finding the optimal agenda of flights.
• In path planning for mobile robot transportation...

This algorithm begins with a root (or start) node and a queue of candidate nodes. At each step, we compute minimal distance between the root and each unvisited neighbors. Then, we add them to the queue; the one with the lowest distance is the next one that will be taken from the queue. This process repeats until a path to the destination has been found.

Since the lowest distance nodes are examined first, the first time the destination is found, the path to it will be the shortest path.

Minimizing the distance from the root node is our heuristic here.

Here is the distance map computed for a maze from the top left corner (root). You may notice that each connection between two adjacent nodes has a distance cost of 1.

## Steps

Let's take a root node and note D the distance from a node to the root. Dijkstra's algorithm will assign some initial distance values and improve them step by step.

• 1. Set all node distance D to infinity except for the root (current) node which distance is 0.
• 2. Mark current node as visited and update D for all of its unvisited neighbours with the shortest distance.
Note: we can stop the algorithm here if we have reached the target node.
• 3. Add to the queue the unvisited neighbours and go back to step 2.
Yes, one of the most useful and used algorithms is as simple as that !

As we have seen : by calculating and continually updating the shortest distance, the algorithm compiles the shortest path to the destination. A key part of this approach is maintaining an ordered line of nodes to visit next; to set up that part of the algorithm, we will use a priority queue (a regular queue with the ability to set priorities).

For Dijkstra’s algorithm, it is always recommended to use priority queue (or heap) as the required operations (extract minimum and decrease key) match with specialty this data structure. Here the priority is defined by D (the distance between a node and the root). Higher priorities are given for nodes with lower distance D.

You may see it as a regular attraction queue with some people having access to shortcut heading to different checkpoints. A priority queue should have the following methods:


// Add new element at the end of the queue
void enqueue(const T& data, const int priority);

// Remove element from the beginning of the queue
void dequeue();

// Change the priority of the element in the queue.
void changePriority(const T& item, const int priority);



Now that we know all we need to know, here is the implementation (the visual explanation follows):

## Code


Dijkstra(Maze maze, Node start, Node end) {
priority_queue queue();

// Init all distances with infinity
for (auto&& node : maze.nodes) node.distance = Infinity;

// Distance to the root itself is zero
start.distance = 0;

// Init queue with the root node

// Iterate over the priority queue until it is empty.
while (!queue.isEmpty()) {
curNode = queue.dequeue();  // Fetch next closest node
curNode.discovered = true;  // Mark as discovered

// Iterate over unvisited neighbors
for (auto&& neighbor : curNode.GetUnvisitedNeighbors())
{
// Update minimal distance to neighbor
// Note: distance between to adjacent node is constant and equal 1 in our grid
const minDistance = Math.min(neighbor.distance, curNode.distance + 1);
if (minDistance !== neighbor.distance) {
neighbor.distance = minDistance;  // update mininmal distance
neighbor.parent = curNode;        // update best parent

// Change queue priority of the neighbor since it have became closer.
if (queue.has(neighbor)) queue.setPriority(neighbor, minDistance);
}

// Add neighbor to the queue for further visiting.
if (!queue.has(neighbor)) queue.add(neighbor, neighbor.distance);
}
}

// Done ! At this point we just have to walk back from the end using the parent
// If end does not have a parent, it means that it has not been found.
}


NOTE
Dijkstra’s algorithm does not support negative distances. The algorithm assumes that adding a relationship to a path can never make a path shorter, an invariant that would be violated with negative distances.
Nodes in all the different directions are explored uniformly, appearing more-or-less as a circular wavefront (as the breadth-first-search) as we use a constant cost of 1 for all connections between two adjacent nodes.

Using a priority queue instead of a regular queue changes the way the frontier expands. Contour lines (based on distances) are one way to see this.

See how the frontier expands more slowly through the forests (source : redblobgames).