地图上计算路线的算法

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:

algorithm Dijkstra(G, S):
    // INPUT
    //    G = a weighted graph
    //    S = the source node
    // OUTPUT
    //    dist = array containing the shortest distances from S to each vertex in G
    //    prev = array containing the predecessors on the paths from S to each node in G

    for each vertex V in G:
        dist[V] <- infinity
        prev[V] <- null
        if V != S:
            Add V to priority queue Q
            
    dist[S] <- 0
    
    while Q is not empty:
        U <- min(Q)
        for each unvisited neighbor V of U:
            tempDist <- dist[U] + edgeWeight(U, V)
            if tempDist < dist[V]:
                dist[V] <- tempDist
                prev[V] <- U
                
    return dist, prev

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

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

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

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

If is smaller than the current shortest distance to , we update the to and sets to . Finally, we repeat the process with the updated priority queue.

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

2.2. Time and Space Complexity

The time complexity of the Dijkstra algorithm is , 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 using a binary heap.

On the other hand, space complexity is . 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.

Algorithm

Pros

Cons

Dijkstra

Guaranteed to find the shortest path between two points.

Can be slower than A* when the target is far away.

Easy to implement and understand.

Doesn’t take into account the location of the target, this can result in inefficient searches.

Works well on graphs with uniform costs (same cost for each edge).

May not work well on graphs with nonuniform costs.

A*

Generally faster than Dijkstra for finding paths between distant points.

Can be more complex to implement and understand.

Can be more efficient on graphs with nonuniform costs.

Requires a heuristic function, which may not always be easy to define.

Takes into account the location of the target, which can result in a more efficient search.

Not guaranteed to find the shortest path if the heuristic function is not admissible (it overestimates the cost to the target).

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:

• Floyd-Warshall algorithm
• Johnson’s algorithm
• Bellman-Ford algorithm
• Prim’s algorithm
• Kruskal’s algorithm

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.