In this blog post, we’ll explain the principles, examples, and real-world applications of Dijkstra’s algorithm in an easy-to-understand way.

Introduction

Think back to the fairy tale “Hansel and Gretel.” When their stepmother abandoned the children in the forest, their first attempt—dropping pebbles to mark their path—failed, and their second attempt—leaving breadcrumbs—didn’t end in failure because the birds ate them. If smartphone navigation or mapping apps had existed back then, the siblings wouldn’t have gotten lost, and their stepmother’s plan would have fallen apart. As this example shows, the problem of “finding the fastest route from a starting point to a destination” has remained a crucial topic throughout history, from ancient tales to today’s technology.

Graphs and Basic Concepts

To understand Dijkstra’s algorithm, we must first define what a “graph” means in the context of computer science. Here, a graph is not a functional graph drawn on a plane, but rather a data structure consisting of a set of vertices and the edges connecting them. For example, if we think of vertices as subway stations or bus stops, the edges become the rail lines or roads connecting those vertices.
Edges may have weights assigned to them; these values represent measurable costs, such as the distance or time required to travel between two vertices. Additionally, if edges have directions, the graph becomes a “directed graph,” where movement is allowed only in the direction of the arrow. Dijkstra’s algorithm calculates the shortest distance and path from a specific starting point to every other vertex in such a graph.

How the Dijkstra Algorithm Works

Let’s explain the algorithm using a common example. The initial value of the starting vertex is set to 0, while the initial values of all other vertices are set to infinity (∞), meaning there is no connection information yet. These values represent “the shortest distance (or time) known so far to reach that vertex from the starting point.”
In the first step (Step 1), we start with the starting vertex set to 0. In the second step (Step 2), for all neighboring vertices directly reachable from the starting vertex, we record a temporary value for each of them by adding the starting vertex’s value (0) to the weight of the corresponding edge. In the example, these values are recorded as 8, 9, and 11. At this point, processing of the starting vertex is complete.
A “processed vertex” refers to a vertex for which no shorter path can be found, meaning its final shortest distance has been determined. In Dijkstra’s algorithm, once the shortest distance to a vertex is determined in this manner, that vertex is marked as processed, and its value is never changed again.
In the third step (Step 3), we select the vertex with the smallest value among the temporary values recorded so far. In the example, the vertex with a value of 8 is selected. Starting from this vertex, the distances from the starting point to this vertex are used to update the values of the surrounding vertices. Through this process, updates occur—for example, the new candidate distances for some adjacent vertices are calculated as 18. Once processing of this vertex is complete, it is also marked as processed.
In the fourth step (Step 4), we process the vertex with the next smallest value—in this example, the one with a value of 9. For this vertex as well, we calculate candidate distances for its adjacent vertices in the same manner. During this process, new candidate values (e.g., 15, 10, 12) may appear for vertices that already have values assigned. If a new value is smaller than the existing one, it overwrites the existing value; otherwise, the original value is retained. This operation is called “edge relaxation,” and it is a necessary procedure because we are always seeking the shortest path.
Starting from the fifth step (Step 5), the same method is repeated. Each time, the vertex with the smallest temporary value among those not yet processed is selected, and the temporary values of its adjacent vertices are updated by relaxing them through the adjacent edges. By repeating this process until all vertices have been processed, we can determine the shortest distances from the starting point to every vertex, as well as the shortest paths.

Application Example: Networks and Routers

Computer networks are a prime example of a field where Dijkstra’s algorithm is widely used in practice. Since it would be inefficient for billions of devices to be directly connected to a single network—as is the case with the Internet—devices in close proximity form local networks, which are then connected to higher-level networks in a hierarchical structure. In such a complex connection structure, there are countless paths from one device to another.
In a network, each node (such as a router) must evaluate paths based on certain costs (bandwidth, latency, etc.) and find the “fastest” or “lowest-cost” path to the destination. Routers use shortest-path algorithms, such as Dijkstra’s algorithm, to determine the optimal path—that is, the next hop—to which they should forward traffic. However, since real-time traffic conditions are constantly changing, it is more practical for each router to provide only information about the immediately next network segment—rather than a router announcing a fixed, complete path—and for each router to update this information on the fly as the path is constructed.

Conclusion: Lessons from Pathfinding

So far, we’ve examined the basic concepts of Dijkstra’s algorithm, its step-by-step operation, and how it’s applied in networks. If Hansel and Gretel had wanted to avoid getting lost in the forest, they would have needed a more reliable method of navigation than simple markers. In fact, algorithms like Dijkstra’s play a similar role when we navigate or transmit data. I hope you’ll keep the ideas behind Dijkstra’s algorithm in mind so you won’t get flustered when traveling an unfamiliar path and can find efficient routes even within complex networks.