Determining the fastest route between two points is a central problem in many application areas: from satellite navigation to network management, from logistics to video games, up to the online maps that we usually consult. At the basis of these applications lie mathematical modelscalled graphsAnd algorithms capable of identifying the optimal route. Among these, one of the most important is theDijkstra’s algorithmwhich allows you to efficiently calculate the shortest path between a starting point and a destination. Most of the navigation systems we use every day are based on this principle.
The optimal route problem
To represent the problem we use a mathematical entity called graphmade up of nodes (or vertices), which represent significant points such as intersections, cities or devices, and from archeswhich instead describe the connections between these nodes. Each arc is associated with a weight; we often tend to interpret this weight as the travel time, but it is actually a more general concept, namely the cost.
The weight of a path, which is a set of arcs and nodes, can refer to several sizes:
- Distance physics
- Time Of voyage
- Consumption of fuel
- Tolls or economic costs
- Level of safety or risk
In real problems, these factors do not act separately, but in combined way. The concept of is therefore introduced in theoretical applications generalized costor a synthetic quantity that integrates multiple variables into a single parameter. The generalized cost does not necessarily have a physical unit of measurement: it is a “normalized” quantity that allows different elements to be compared with each other. In other words, a single indicator is constructed that represents the overall behavior of the system.
For example, a navigator can combine travel time, traffic conditions and energy consumption. The problem then becomes find the path that minimizes the total generalized costnot necessarily the time.
How Dijkstra’s algorithm works
Dijkstra’s algorithm is a procedure that, starting from a initial node and identified a final nodelocate the least cost path to the other nodes of the graph up to the arrival node. It is based on a so-called approach greedy (literally “greedy”) who, at every step, chooses the locally best solutionprogressively building the global solution. To understand how it works, we can imagine the algorithm scheme divided into four logical phases:
- Initialization: a cost of zero is assigned to the starting point, while all the other nodes of the graph are initially treated with infinite cost, since we do not yet know how to reach them.
- Selection: among all the nodes not yet analyzed, the one with the lowest recorded cost is chosen. This node becomes our current reference point and represents the most convenient route known up to that point.
- Update: the nodes directly connected, via arcs, to the current node are analysed. For each of them, it is verified whether, passing through the current node, a lower total cost is obtained than that recorded previously. If the new route is cheaper, we update the cost value and note the current node as the “previous step”. This will ultimately serve to reconstruct the optimal path (i.e. the solution) backwards. Once the verification is completed, the reference node is marked as definitive, as we are certain that the cost to reach it can no longer improve.
- Iteration: the selection and update steps are repeated until the final destination is reached or the nodes to be analyzed run out.
The algorithm can be visually imagined as awave that propagates in concentric circles starting from the initial node. This expansion first extends to the lowest-cost nodes and, step by step, maps the entire network. This mechanism guarantees that a node is “fixed” as definitive only when it is mathematically certain that the path found is the most efficient of all.
However, this logic based on the progressive expansion of the wave also reveals the main one theoretical limit of the algorithm: the need for all costs (edge weights) to be positive. If negative costs existed, a path that was initially longer and discarded by the wave could suddenly turn out to be cheaper at a later time, throwing the entire selection process into crisis and preventing us from considering any node just visited as “definitive”.
Applications, complexity and limitations
Dijkstra’s algorithm is a cornerstone of computer science for simplicity and robustness and is still widely used today in numerous fields, such as navigation systems (calculation of optimal routes on the road network with GPS), theogistics (optimization of delivery routes), computer networks And artificial intelligence. The performance of the algorithm depends on the data structures usedso that the simpler its implementation, the less efficient the algorithm and therefore its solution times. However, despite the advantages, there are some limitations. As mentioned before, the algorithm it doesn’t work with negative weights. Furthermore, it can be burdensome on very large graphs without proper optimizations and has the constraint of require a single starting source: for more complex problems variations are therefore necessary.
Sources
Cascetta E. – Models for transport systems. Theory and Applications
