In this blog post, we’ll explore the principles and applications of Dijkstra’s algorithm—the route-finding algorithm behind navigation systems.
Chul-soo, who had just enrolled at Seoul National University, was on his way to the gymnasium for the orientation ceremony. However, he was so excited that he got on the wrong bus and ended up getting off deep within the campus. Fortunately, Chul-soo had a student handbook with a map, but the map was so complicated and large that it was difficult to find his way quickly. Worried he might be late for the orientation ceremony, Chul-soo was confused because he couldn’t figure out which route was the fastest. If Chul-soo had had a navigation system instead of a map, he wouldn’t have had to worry about this.
How does a navigation system find the shortest route? The reason is that navigation systems contain algorithms designed to find routes. An algorithm refers to a set of procedures for solving problems such as finding the shortest path, and it typically provides a method for solving problems using a computer. Even a simple method—such as calculating the time required for each route and selecting the one with the shortest time—can be considered an algorithm. However, this method takes too long to find the shortest path, making it impractical for real-world use. Therefore, finding more efficient algorithms is one of the key concerns in computer science.
Let’s take a look at Dijkstra’s algorithm, a representative algorithm for solving the shortest path problem. Dijkstra’s algorithm assumes that there are multiple locations—such as “Seoul,” “Incheon,” and “Busan”—and that the travel time between any two adjacent locations is already known. First, the point closest to the starting point is considered to have its shortest path already determined. Next, among the points for which the shortest path has not yet been determined, the one closest to the starting point is identified. In this process, paths that pass through points where the shortest path has already been determined are also considered. By determining the shortest path to the nearest point one by one in this manner and repeating the process, we can eventually find the shortest paths to all points.
Let’s look at an example to help illustrate this. First, assuming we know the travel time between two adjacent points, we’ll find the shortest route from Seoul to Busan.
Of the two cities adjacent to Seoul—Daejeon and Daegu—Daejeon is closer to Seoul. Therefore, we know that no matter which route is taken, it is impossible to travel from Seoul to Daejeon in less than 2 hours.
Next, we examine the points adjacent to Daejeon. These are Daegu and Changwon; in the case of Daegu, it is faster to travel via Daejeon than to go directly from Seoul. In this case, the travel time from Seoul to Daegu is 4 hours, which is the shortest time among the points for which the shortest route has not yet been determined. Therefore, we determine the shortest route to Daegu and proceed to the next step.
Similarly, among Changwon and Ulsan—which are adjacent to Seoul, Daejeon, and Daegu—Changwon is the fastest to reach from Seoul, taking 6 hours via Daegu. Next are Ulsan and Busan, with the shortest travel times for each confirmed at 7 hours. Ultimately, we can see that the shortest route from Seoul to Busan is “Seoul–Daejeon–Daegu–Changwon–Busan,” taking a total of 7 hours.
The Dijkstra algorithm solves the shortest path problem efficiently in this way. For example, once it is confirmed that traveling via Daejeon is faster than going directly from Seoul to Daegu, the algorithm no longer considers inefficient routes like “Seoul–Daegu–Changwon–Busan” in subsequent calculations. Therefore, it can find the shortest path much faster than a simple algorithm that calculates every possible route one by one.
However, the maps used in actual navigation systems consist of countless roads, both large and small, resulting in a very large number of roads. Consequently, simply applying Dijkstra’s algorithm as is can still lead to lengthy computation times. To address this issue, real-world navigation systems employ various optimization techniques: they first calculate the route focusing on major roads such as highways, and then additionally calculate the segments connecting the starting point to the major roads, as well as the segments connecting the major roads to the destination.
For example, if you’re traveling from your home in Seoul to a relative’s house in Busan, the system first calculates the route from Seoul to Busan using the highway, and then separately calculates the routes from your home to the highway entrance and from the highway exit to your relative’s house.
Route-finding features on navigation systems and the shortest-path search on subway maps are functions we use frequently in our daily lives, and in-car navigation systems also operate based on this technology. At first glance, the process of finding a route may seem very complex, but if you examine the principles step by step, Dijkstra’s algorithm is quite understandable. Understanding the principles of this algorithm will make it much easier to grasp how navigation systems find routes.
