In this blog post, we’ll take a simple look at the principles behind finding the shortest-time route on the subway using a network model and how the “Dijkstra’s algorithm” works.
Seoul’s subway system, which began with the opening of Line 1 on August 15, 1974, has evolved into a large-scale urban rail network connecting the entire metropolitan area through continuous route expansion and system improvements. The subway system has also steadily advanced, allowing users to easily access various information—such as real-time train locations and estimated arrival times—anytime, anywhere. Most subway riders use the internet or smartphone apps to find the fastest route to their destination. When you enter the departure and arrival stations, the fastest route is immediately suggested—but how is this route calculated?
One of the most common ways to model this problem is through a network model. A network model is a tool that visually represents complex, interconnected systems—such as those in transportation, logistics, supply chain management, and information and communications technology—to make them easier to understand. The problem of finding the shortest-time route on the subway can also be effectively modeled using a network model. This model serves as the foundation for finding the shortest-time route and is used to calculate which specific route will allow a passenger to reach their destination in the least amount of time. So, let’s take a closer look at what a network model is and how it is used to find the shortest travel time route on a subway system.
A network model is broadly composed of nodes and arcs. Nodes represent key points, starting points, or facilities; in a subway system, they correspond to individual stations. Arcs are lines connecting nodes, and in a subway system, they represent the connections between stations. Generally, arcs connect adjacent stations. Since a network model can represent a system using only these two elements—nodes and arcs—it offers the advantage of visualizing the system simply yet effectively. Additionally, in a network model, flow occurs as it moves from node to node along the arcs, and the ultimate goal is to find the shortest-time path for this flow. Here, the meaning of “flow” varies depending on the type of system; in a subway system, it refers to the movement of trains between stations. In other words, the ultimate goal is to determine which nodes to pass through and which arc to follow to travel from the origin to the destination in the shortest amount of time.
Each arc is assigned a number, which is referred to as the “cost.” Depending on the type of problem, the cost can represent various values such as distance or time. Since the time taken to travel between stations is the key factor in a subway system, we can consider the cost to be time in this context. For example, if the arc connecting node 1 and node 2 is labeled with the value 3, this means it takes 3 units of time to travel from Station 1 to Station 2.
This network model is ultimately designed to determine which path takes the least amount of time to travel from Node 1 to Node 7. A problem aimed at finding the shortest path or the shortest travel time in this manner is called the shortest path problem. Such problems can be solved using the “Dijkstra’s algorithm.” Let’s now take a closer look at the specific process of finding the shortest path using this network model.
An algorithm refers to a series of logical operations that a computer can perform, and it generally consists of an initialization phase and an iterative phase. Initialization is the process of setting initial values and defining necessary variables before the iterative phase, while the iterative phase involves finding the target value according to a predetermined procedure. In “Dijkstra’s algorithm,” each node has a field to store the shortest time so far, and initially, all values are set to infinity. However, node 1, the starting point, is initially set to 0. In the initial state, the shortest time from node 1 to node 1 is 0, so it is set to 0; the values for the remaining nodes are gradually updated to smaller values during the iterative process. When the algorithm terminates, each node records the shortest time from the starting point.
The first step in the iterative process is to select the node with the smallest current value. Initially, since the smallest value is 0, node 1 is selected. Next, the values of the neighboring nodes connected to node 1 are updated. For example, since it takes 3 units of time to reach node 2 from node 1, its value becomes 3. After updating the values of all connected segments, the selected segment 1 is designated as a fixed segment that will no longer be selected.
Next, segment 3—which has the smallest value among the unfixed segments—is selected. The values of the segments connected to segment 3 are updated again, this time based on the shortest time to segment 3, which is 2. For example, if it takes 4 units of time to move to node 5, the new candidate value is 6—the sum of the shortest time to node 3 (2) and the travel time (4). In this way, after comparing the values of all connected nodes and updating them as necessary, node 3 is also designated as a fixed node.
Next, node 2, which has the smallest value, is selected. However, even if moving from node 2 to node 3, node 3 already has a shorter time of 2 recorded, so the value cannot be updated to a smaller number. Therefore, no new value is reflected in this step, and node 2 also becomes a fixed node. This process is repeated until all nodes become fixed nodes, at which point the algorithm terminates. Using the final calculated values, we can determine which nodes to pass through from the starting point to the destination to achieve the shortest travel time. In this example, the shortest path is the route starting from Node 1, passing through Node 3, and ending at Node 5, which takes a total of 5 units of time.
So far, we have examined the structure of a network model and how to find the shortest path using the “Dijkstra’s algorithm.” A network model is a tool that helps us efficiently solve problems by representing complex systems—such as subway maps—in an easily understandable way. Furthermore, “Dijkstra’s algorithm” is a representative algorithm that finds the shortest path by calculating desired values step by step based on the network model. While this algorithm has the advantage of allowing users to visually verify and understand the problem-solving process, it requires a significant amount of time to calculate large-scale problems manually. In practical applications, this algorithm is implemented as a computer program to calculate the shortest path in a very short amount of time. As such, network models are important tools for effectively visualizing complex systems and efficiently obtaining desired results, and they are widely used in various fields, such as subway systems.
