In 1959, Edsger Wybe Dijkstra created an algorithm known as the “Shortest-Path Algorithm”, which was (and still is) the basis for the creation of several other specific and improved algorithms.
The Shortest-Path algorithm does not use the real position of the points to compute the path. Instead, it uses the connections between nodes and the values that are associated with them (costs). The real position of the points is only used after you get the computed path in order to visually move the objects inside the game.
The main idea of the algorithm is to check all the neighbours of the starting node and store the shortest distance, repeating this step with the neighbours of its neighbours, until the shortest path to the end node is eventually found. The algorithm marks each processed node as “visited” when the shortest path to them is calculated, at the same time it stores the closest neighbour to this node (the previous node in the path). Finally, when the end node is processed, it’s possible to get the full path using all stored previous nodes (as if the path was calculated backwards).
Let’s use the scenario shown in the image below to understand how the algorithm works. Notice that the graph is weighted, that means, each node connection has an associated value to it (cost). Because of that, it is possible to represent any factor that influences the movement of objects (terrain, traffic, etc..).
Let’s say we want to compute the path from node A to G.
The algorithm uses three arrays to calculate the shortest path. The first array stores, for each node, if its shortest path has already been found. The second array stores the minimum distance to each node. Finally, the last array stores the previous node of the path, for each node of the graph.
The next image shows the arrays with initial values. The algorithm fills the third array with the starting node (node A) and the distance vector is filled with the known distance between the starting node and the others. In addition, node A is already marked as “found” because the distance to itself is zero (it’s just impossible to have a smaller distance than that).
According to what the graph represents, it’s correct to say that among the neighbours of A, node C has the shortest distance to it. Based on this info, it’s possible to conclude that there would be no shorter path to the node C starting from node A. The only other possible path (A-B-C-D) would cost much more.
So the second step of the algorithm is to check the arrays and find, from the nodes that are not yet marked, which one has the lowest distance (in our case, node C). The algorithm then considers that the shortest path to this node was found and updates the arrays as shown in the next image.
If the node C was the end node (the goal), we could stop here. But because we want to find node G, the algorithm continues and executes the third step.
The third step consists of, for every unmarked node, verifying if there’s a better distance coming from the found node C and then update the arrays with the new information.
As for example the node D, whose distance was initially set to “infinite” (because of the info we had from the node A). We can now say that the distance from the node D via the node C is seven (minimum five to node C, coming from A, plus two until the node D). Therefore, the distance array is updated with seven, and the previous node array is updated to node C, as shown in the image below.
After performing step 3, the algorithm executes the second step again. From the unmarked nodes, the one with the shortest distance is selected and marked as found. In this example, nodes B and D have equal distances (seven), but even if node D is visually “closer” to the end goal, the algorithm will process node B (since it’s the first one in the array). On improved algorithms, there’s a better way to select which nodes to process first.
After B is then marked as found, step 3 is performed again. The next image shows how the arrays look after this iteration. Notice that, despite the connection between nodes B and D, the previous node for D won’t be changed because the path for node D passing through B would cost more than the path through C. But as long as a node is not marked as found, the minimum known distance can be changed for a better one (as it happened with node F).
If we continue repeating these steps, the end node G would be eventually found and the arrays would be ended as shown in the next image. Try to do the algorithm until the end to see if you are able to get the same result.
After finding the minimum distance to the node G, the algorithm finally executes the final step, which is to organize the response with the sequence of nodes that compose the minimum path from A to G.
Using the array of previous nodes, the algorithm verifies that the previous node for G is the node F. Then, the previous node for F is the node D. The algorithm continues until it finds the starting node A. The final result will be the path G-F-D-C-A, which is then reversed to form the shortest path from node A to node G (A-C-D-F-G).
The next image presents a minimalist implementation of the Dijkstra algorithm in pseudo-code.
On the next post I’ll talk about a better version of Dijkstra, that was created to be used on game development: the A-Star algorithm.