In algorithmic problems involving graphs, we use several well-known algorithms. Two of them are graph traversal algorithms: Breadth First Search and Depth First Search. And two more, A* and Dijkstra’s algorithm, are used when we want to find the optimal path from one node to another within a graph.

In this article, I will show that all of these four algorithms are actually the one algorithm, and the difference between them is only achieved through the different data structures used to store the unvisited nodes of the graph.

Graph path finding problem

First, we consider the problem of finding the way inside a small simple graph shown in the figure. Moving from node to node, we want to find a path from the node labeled “start” to the node labeled “target”.

The most obvious thing we can do is to use one of the well-known search algorithms: depth-first or breadth-first. Let’s describe a typical algorithm for finding a path between two nodes in a general way.

The one and only algorithm

We begin with the start node and can move along the edges of the graph to neighbouring nodes. At every iteration of the algorithm, we have some current_node our attention is focused on. We explore its neighbors, i.e. the nodes connected with the current one and those that we can potentially move to in the next iteration. We save all neighbors of the current_node in a separate set of nodes unvisited yet, but with the known path to them. This set is a special storage of unvisited nodes, from which we can choose where to go next.

For the current_node, we check if it is the target, and if it is, it means that we have arrived — the desired path has been found. The search algorithm can be interrupted. Otherwise, we must consider the nodes adjacent to the current one and add them to the nodes_storage described above.

To avoid confusion and not come to the same node several times, we usually color the nodes:

• white color means that we have not visited or even met this node yet;
• gray — we have met this node as an adjacent one and have already added it to nodes_storage, but it was not visited yet;
• black — this node has been visited and no longer needs to be reviewed.

Initially, all nodes are white. If we encounter a node (i.e. it is a neighbor of the current_node under consideration) we color it gray. And only when we have visited a node, processed all its neighbors, and it is no longer useful, we can paint it black.

A separate important case is when we met a non-white neighbor. This means we have already reached this node in a different way, and now we need to resolve the conflict between these two paths. Because we often want to find the shortest path, the solution is to choose the path with the shortest distance.

No more words, code please

Now that we’ve described the algorithm in general terms, it’s time to dive into the code a. Let’s write this algorithm in Python.

For now, we will not specify the data structure for storing unvisited nodes, calling it AbstractNodeStorageClass. We only need to know that this class has three methods: insert — to add node to the storage, get_first — to extract one element from the storage, and is_empty — to check if the storage is empty.

That’s all! This is the only algorithm we are going to use. By substituting different data structures as a data store, we will obtain different classical algorithms on graph.

Depth-First Search

If we use a Stack as a nodes_storage, the algorithm written above turns into a depth-first search.

Let’s check. Below is the class implementing the storage of unvisited nodes according to the Stack principle, i.e. get_first method returns the element added the last.

And the result of using this class is shown below. The animation shows that on each iteration we are digging as deep as possible looking for the target node.

Breadth-First Search

In order for the search to be performed in breadth, you need to use a queue instead of a stack.

The only difference with the Stack is taking the first element with pop(0) function instead of taking the last one using pop(). The result is shown below.

Notice how instead of going deeper with each new node, we now are going through all the nodes located on the same horizontal, i.e. iterating over the nodes as widely as possible. And also notice, how target node going through the queue.

Dijkstra’s algorithm

Initially, Dijkstra’s algorithm was designed to find the shortest path to a given node (and to all the others at the same time), starting from some initial node. We can apply it to our problem of finding a path between two nodes. But before that, let’s make it more interesting and add a distance parameter to every edge of the graph.

This means the edges will have different lengths, and the distance between nodes 0 and 1 is three times greater than the distance between nodes 0 and 2.

Now let’s write down the data structure of nodes storage for Dijkstra’s algorithm - the priority queue. The main difference of this queue is that the get_first method selects the node with the smallest distance from the start node.

The result of our algorithm on such a data structure is as follows.

It is interesting to note that in three cases we obtained three different paths within the same graph using the same algorithm.

Finding a way out of the maze

Before we go further, it’s time to complicate our task even more and replace a simple graph with a maze. The start and target nodes are the entrance and exit of the maze respectively, and the rest of the available space is filled with graph nodes. Our goal is to find a path from the entrance to the exit through the graph.

Let’s see how Dijkstra’s algorithm solves this problem. Without changing neither algorithm nor data structure from the previous paragraph, let’s feed a new graph as the input.

We see how the algorithm iterates over the nodes sequentially, with each next node being selected according to the principle of priority queue — every node taken from the storage is the closest to the start one.

Using this approach, we have to iterate over almost all the nodes in the maze. Although intuitively it seems that we can do better if we aim towards the target node. It was this kind of reasoning that led to the creation of the A* algorithm.

A* algorithm

Algorithm A*, in addition to the distance from the start node (which is calculated along the path shown in green), also takes into account a rough estimate of the distance to the target node. This approximate estimate is calculated as the Euclidean distance from the selected node to the target one. The only change we need to make is the calculation of the node’s priority within the priority queue. Here is the code:

Here we see an additional method calc_heuristic() that estimates the distance to the target node. Now we will give this data structure to the algorithm and get the following result:

Note that due to heuristics, the A* algorithm finds the correct answer faster (80 steps instead of 203).

Instead of conclusion

It was shown above that for the problem of finding a path in a graph, four different classical algorithms can be applied. Moreover, in this case they turn into one algorithm and all the difference between them is only in the data structure used. The table below summarizes this idea.

If you liked the article, you can watch the full tutorial and play with the code in google colab or see the whole code on github.

And also don’t forget to clap and follow.