Algorithms for Computing Routes on a Map | Baeldung on Computer Science

1. Introduction

In this tutorial, we’ll give details on how routing algorithms work under the hood while trying to find our way in our daily life. Before getting into details about algorithms, let’s take a look basic step of how we compute a path on a map.

Firstly, we need to define a start and end point. After that, we should look at the map and identify the available routes between the starting point and the destination. We may have options like roads, highways, tunnels, and bridges.

What to do next is to evaluate the options and consider factors like traffic, potential roadblocks, or obstacles. After we evaluate the available options, we choose the best route for our needs.

So, this was the general way of finding our path. In computing, maps are represented as graphs and there are several algorithms for finding the shortest path between nodes in graphs.

For example, map applications that we use to find our way in daily life usually use algorithms based on the Dijkstra algorithm. They usually combine different algorithms and techniques to calculate the best routes between two or more locations. However, the main algorithm usually is constructed on Dijkstra’s algorithm. That’s why for the sake of this article, we’ll analyze the Dijkstra and A* star algorithms in detail.

2. Dijkstra’s Algorithm

This algorithm is named after its inventor, computer scientist Edsger Dijkstra. In 1959, he defined the algorithm in his paper “A note on two problems in connexion with graphs“. Dijkstra developed this algorithm as a solution to the shortest path in a road network. Especially for the routes between Rotterdam and Groningen cities. He also mentions that he didn’t even use pencil and paper while inventing this algorithm.

This explanation actually shows the simplicity of the algorithm and its impact too. It became widely popular in the field of computer science and has been widely used in a variety of applications. For example, from network routing, and resource allocation to data compression.

2.1. Pseudocode

Let’s take a look at how the algorithm works from its pseudocode below:

This algorithm takes as input a weighted graph $G$ and a starting node $S$ . The main goal of the algorithm is to compute the shortest between $S$ and every other node in $G$ .

We first initialize two arrays $dist$ and $prev$ . $dist$ will store the shortest distance from $S$ to each node in $G$ . On the other hand, we use prev to keep track of the previous node on the path from $S$ to each node. The distance from $S$ to itself is 0, and there is no previous node for $S$ . That’s why $dist[S]$ will be set to 0 and $prev[S]$ will be set to null.

In this pseudo code, we initialize a priority queue $Q$ containing all the nodes in $G$ . The priority of a node in $Q$ is the current shortest distance to that node from $S$ .

We repeat the steps until the priority to queue is empty. In each iteration, select node $U$ in $Q$ with the smallest value and remove it from $Q$ . For each unvisited neighbor of $V$ of $U$ , we compute a tentative distance $tempDist$ from $S$ to $V$ by adding the length of the edge from $U$ to $V$ to the current shortest distance to $U$ .

If $tempDist$ is smaller than the current shortest distance to $V$ , we update the $dist[V]$ to $tempDist$ and sets $prev[V]$ to $U$ . Finally, we repeat the process with the updated priority queue.

After the while loop finishes, we return the arrays $dist$ and $prev$ that contains the shortest distance from $S$ to every node in $G$ and the previous node on the path from $S$ to each node.

2.2. Time and Space Complexity

The time complexity of the Dijkstra algorithm is $O(V^2)$ , where V is the number of nodes in the graph. However, if the graph is represented using an adjacency list, time complexity will be reduced to $O(E log V)$ using a binary heap.

On the other hand, space complexity is $O(V)$ . The reason for this is we have to store all the vertices in the list as an output. As we’ve expected, the time complexity can be enormous when the graphs are getting bigger and bigger. That’s why in today’s applications different kinds of optimizations are applied.

3. A* Algorithm

The A* (A-star) algorithm is an extension of the Dijkstra algorithm. It has a heuristic component to guide the search toward the target node. It is widely used in path-finding applications such as robotics, map applications, and video games. A* is often preferred over the Dijkstra algorithm because it can be faster when there is a good heuristic that guides the search toward the target node.

3.1. Comparison of A* and Dijkstra’s Algorithms

A* is a specific-goal-oriented algorithm. It means that it only finds the shortest path from a specific source to a specific goal. In contrast, Dijkstra’s algorithm finds the shortest path tree from a specified source to all possible goals. Since the A* algorithm uses a heuristic to guide the search toward the goal, it can be more efficient than Dijkstra’s algorithm when the goal is known and the heuristic is efficient. However, the use of a heuristic means that the algorithm may not explore all the paths. This will affect the finding of the shortest path if the heuristic is not admissible.

In contrast, Dijkstra’s algorithm guarantees to find the true shortest path from the source to all possible goals. On the other hand, this will cause the exploration of so many unnecessary paths and as mentioned earlier could be inefficient for large graphs. Therefore, the choice between A* and Dijkstra’s algorithm depends on the specific problem and the heuristics. If the goal is known and there is an efficient heuristic function or graph has negative edges, A* can be more efficient. However, if we don’t know the goal or the heuristic is not effective, Dijksta’s algorithm may be the better choice.

4. Other Shortest Path Algorithms

In some cases, Dijkstra or A* may not be the best solution either. Some of the other common-use algorithms are:

5. Conclusion

In this tutorial, we’ve analyzed two of the shortest path algorithms, Dijkstra and A*. We’ve looked at how Dijkstra’s algorithm works and when we have more sophisticated algorithms such as A*. We also compared the A* and Dijkstra’s algorithms and which one will be more efficient in which case. It should be kept in mind that these algorithms paved the way for so many discoveries.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex