 Illustration by Alyia Vasquez By Amrita Acharya When traveling to a new place, most of us will probably pull out our phones and use its maps to find the best route to get there. But how do these navigational apps really find this best route? The most obvious approach might seem to be finding all possible routes and choosing the shortest option from them. At first glance, this simple algorithm seems like the best solution. However, this approach quickly becomes time-consuming and computationally expensive when the map gets large. So how do we improve this and find a better algorithm? The solution lies within graphs. A graph is a data structure made up of nodes, where the nodes hold pieces of data and are connected by edges. Graphs are incredibly useful, especially when modeling situations with relational objects (Graphs, n.d.). In our case, nodes would represent various locations on the map, and edges would be the roads between them. Graphs can also be weighted; each edge is assigned a “weight” (or “cost”) of traveling along that edge. For instance, let’s say edge A represents a highway. Highways are often preferred to other roads due to their faster travel speed, and therefore, will be assigned a lower cost. The weight here reflects the desirability of taking that route.
The key to solving our map problem could be found in the solution to the single-source shortest paths problem” (SSSP problem) – the shortest path from a given starting node to all the other nodes in the graph (Bhattacharyya, 2023; Shortest Path Problem, n.d.). In 1956, Edsger Dijkstra came up with an algorithm to solve the SSSP problem. He did so in twenty minutes. No pen. No paper. For nearly 70 years, this algorithm was the fastest for solving the SSSP problem (Frana & Misa, 2010). At a high level, Dijkstra’s algorithm attempts to make the most optimal choice by exploring every possible next step that it can take from its current location – all the nodes connected to the current node – and then selecting the node with the lowest weight. This optimizes the path length at each step by keeping it as low as possible. It repeats these steps until a path to every node has been found (Cormen et al., 2022, pp. 620–622). The beauty in Dijkstra’s algorithm lies in its simplicity; its ease to understand and implement. The original paper Dijkstra published on this – “A note on two problems in connexion with graphs” – is hardly three pages long (Dijkstra, 1959). He expressed that designing algorithms this way kept him from getting bogged down by the details of the complexities of the problem (Frana & Misa, 2010). While this was surely a good strategy for progress, it did not guarantee algorithmic efficiency. When analyzing algorithms, we look at something called their time complexity – the worst-case runtime of the algorithm. In other words, for a large input size, what is the longest time the algorithm will take to run? (Cormen et al., 2022, p. 50) You might be wondering why we care so much about time complexity? For one, the more time efficient the algorithm, the less the user has to wait for the solution. Imagine waiting 20 minutes for your Google Maps to tell you the quickest route to the closest McDonalds! Let’s consider a simple example: Sequential search is an algorithm that looks for a specific element (the ‘target’) in a collection of elements. It begins at the first element, checks if it is the target, moving to the next element if it isn’t, and ending early and stating success if it is (Weiss, 2009, pp. 207–208). To think about sequential search’s time complexity, we need to consider a few cases. In an ideal world, the element we’re searching for will be the first one we check, implying we can stop searching right away since we’ve already found a match. However, this often isn’t the case, and indeed, when it comes to analyzing runtimes, the best-case scenario isn’t of much use. What we’re more interested in is how the algorithm performs in the worst-case scenario. For sequential search, this would be if the element doesn’t exist in the collection. In this case, we’d have to look at every single element in the collection and reach all the way to the end before we can say that the target element is not found. This means that sequential search’s worst case is n operations if the algorithm is used on an input collection with n elements (Weiss, 2009, pp. 207–208). Until now, Dijkstra’s algorithm has been the most efficient algorithm for solving the SSSP problem since its creation (Cormen et al., 2022, pp. 623–624). In July of 2025, a new algorithm, the Bounded Multi-Source Shortest Paths algorithm, with better efficiency was written. The article’s only been published online, but it spread through the computing world like wildfire. While it does not have the simplicity of Dijkstra’s algorithm, it is undoubtedly faster. Its key to this improved efficiency is that less time is spent processing each vertex by breaking groups of nodes into smaller clusters and keeping those clusters sorted rather than re-sorting every single node each time to find the closest one (Duan et al., 2025; Kumar et al., 2025). Will this new algorithm end up replacing Dijkstra’s algorithm? Only time will tell. But if anything, this illustrates one of the great trade-offs in computer science – that between speed and simplicity. References Bhattacharyya, S. (2023, September 11). How Is Dijkstra’s Algorithm Used In The Real World? | Analytics Steps. https://www.analyticssteps.com/blogs/how-dijkstras-algorithm-used-real-world Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th Edition). The MIT Press. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271. https://doi.org/10.1007/BF01386390 Duan, R., Mao, J., Mao, X., Shu, X., & Yin, L. (2025). Breaking the Sorting Barrier for Directed Single-Source Shortest Paths (Preprint No. arXiv:2504.17033). arXiv. https://doi.org/10.48550/arXiv.2504.17033 Frana, P. L., & Misa, T. J. (2010). An interview with Edsger W. Dijkstra. Commun. ACM, 53(8), 41–47. https://doi.org/10.1145/1787234.1787249 Graphs. (n.d.). Ada Computer Science. Retrieved October 9, 2025, from https://adacomputerscience.org/concepts/struct_graph Kumar, A., Thompson, T., & Ghosh, S. (2025, August 21). The new Dijkstra’s algorithm: Shortest route from data to insights (and action)? [Newsletter]. Modern Data 101 on Substack. https://moderndata101.substack.com/p/the-new-dijkstras-algorithm-shortest Shortest Path Problem. (n.d.). NVIDIA Developer. Retrieved October 9, 2025, from https://developer.nvidia.com/discover/shortest-path-problem Weiss, M. A. (2009). Data Structures & Problem Solving Using Java (4th Edition). Pearson.
0 Comments
Leave a Reply. |