By Tech Target 
The most effective method for determining a graph’s optimal paths was long believed to be Dijkstra’s Map Algorithm. It has now been demonstrated by researchers to be “universally optimal.” You’ve most likely chosen what appears to be the optimal route if you’ve been doing the same commute for a while. But “best” is a nebulous term. Your fastest route can become the slowest one day due to an accident or road closure.
Researchers who create algorithms—the methodical processes that computers employ to solve problems—also face difficulties with scenarios like these. Any given problem may be solved by a variety of algorithms, yet it can be excruciatingly difficult to determine which is the best.
Consider an algorithm that is intended to determine the quickest path between two locations, for instance. Such an algorithm may be designed in a variety of ways to ensure that it is successful. Whether you utilize it in Los Angeles or London, during rush hour or at night, a good algorithm will always offer the quickest path.
However, their algorithms differ from one another. Where and when each algorithm is employed will affect how long it takes to get the correct answer, and situations that are challenging for one algorithm could be simple for another. An algorithm that consistently outperforms the others is ideal.
Finding such a unicorn is just not feasible for the majority of issues. However, a recent demonstration demonstrates that one method is nearly perfect for the classic path-finding problem: It is the optimal strategy on all feasible street grids, assuming the worst traffic patterns. Furthermore, the algorithm has been a mainstay of undergraduate computer science curricula for about 70 years.
Next week, the 2024 Symposium on Foundations of Computer Science will reward the new study with a best-paper prize. “It’s incredible,” Columbia University computer scientist Tim Roughgarden remarked. “There isn’t a more interesting research paper about a problem we teach undergraduate algorithms students.”
Read More: The Samsung Galaxy S25 may feature an Exynos processor
Boundaries and Heaps
This famous path-finding algorithm’s tale started with a detour. Edsger Dijkstra, a 26-year-old Dutch computer scientist, set out to create a program in 1956 that would demonstrate the capabilities of a brand-new computer known as the ARMAC. He took a break at a café in Amsterdam when he and his fiancée were shopping. At that point, he came up with the concept for the algorithm that is today named after him. Since he was without writing supplies, he spent twenty minutes figuring out the specifics in his mind.
Dijkstra said in a final interview that the peculiar beginning of his algorithm contributed to its lasting appeal. “You are practically forced to avoid all avoidable complexities without a pencil and paper,” he stated.
Dijkstra’s method provides more than just the quickest path to a single location. Rather, it solves what experts refer to as the single-source shortest-paths problem by providing you with an ordered list of journey times from your present place to every other site that you would wish to visit.
The technique operates on a graph, which is an abstracted road Map Algorithm consisting of a network of connected points (called vertices) with weights assigned to the connections between vertices. These weights can vary based on traffic patterns and may indicate the amount of time needed to travel via each route in a network. It takes longer to travel that journey with a heavier weight.
To understand Dijkstra’s method, picture yourself exploring a network and noting on a piece of scratch paper how long it takes to get from your starting point to each new vertex. The nearest vertex you haven’t yet visited should be your first pick when deciding which way to explore next. Note the new time and cross out the previous one if you find a quicker way to any vertex.
Transfer the journey time from your notes to a different, more aesthetically pleasing list if you are certain that you have discovered the quickest route. Erik Demaine, a computer scientist at the Massachusetts Institute of Technology, praised the method as excellent. “It’s incredibly quick, straightforward, and simple to implement.”
To put this technique into effect, you’d need to settle on a mechanism for organizing your notes—a data structure, in the terminology of computer science. That might seem like a small technical issue, but the amount of time you spend going through your notes each time you need to change or delete an entry can significantly impact the algorithm’s total runtime.
The data structure utilized in Dijkstra’s study was basic and might have been improved. Better ones, lovingly called “heaps,” where certain objects are simpler to discover than others, were created by researchers in the next decades. They exploit the fact that the nearest remaining vertex is the only one for which Dijkstra’s algorithm ever needs to delete the entry.
Václav Rozhoň, a researcher at the Institute for Computer Science, Artificial Intelligence and Technology (INSAIT) in Sofia, Bulgaria, explained that a heap is essentially a data structure that enables you to accomplish this extremely efficiently.
Dijkstra’s method was able to achieve a theoretical limit, or “lower bound,” on the amount of time needed to solve the single-source shortest-paths issue in 1984 because to a creative heap design created by two computer scientists. This is the best variant of Dijkstra’s algorithm in one particular way. For over 40 years, that was the last word on the typical version of the problem. Only until a few researchers looked more closely at what it meant to be “best” did things start to shift.
The Best Conduct
When comparing algorithms, researchers usually look at how well they perform in the worst-case situations. Imagine the most complicated street layout in the world, then add some very puzzling traffic patterns. The 1984 version of Dijkstra’s algorithm is demonstrably incomparable if you insist on determining the quickest paths under these severe conditions.
Hopefully, though, the street grid in your city isn’t the worst in the world. Therefore, you could wonder: Is there an algorithm that works flawlessly on all road networks? Making the cautious assumption that any network has worst-case traffic patterns is the first step in providing a solution to this query. Then, assuming the worst possible weights, you want your algorithm to identify the quickest routes through each feasible graph architecture. This state is referred to by researchers as “universal optimality.”
You could avoid rush hour traffic in any city on the planet if you had an algorithm that was universally optimum for the more straightforward task of just moving from one point on a graph to another.
Bernhard Haeupler, a computer scientist connected to INSAIT and the Swiss Federal Institute of Technology Zurich (ETH Zurich), commented, “This sounds too good to be true.”
In the mid-2010s, Haeupler was drafting a grant proposal when he got enthralled by the prospect of universal optimality. That aspect of the work is boring to many scholars, but Haeupler saw it as a chance. “It enables you to let go of your doubts and simply have big dreams,” he stated.
When Haeupler and two graduate students demonstrated in 2021 that it was feasible to create universally optimum algorithms for a number of significant graph issues, those hopes were realized. He didn’t consider asking if the traditional single-source shortest-paths problem might be solved using the same condition. Until another graduate student had the courage to dream large, it would have to wait.
Read More: Scout Motors establishes ties with its new Traveler SUV and Terra electric vehicle
The Quickest Way to Win
Rozhoň was nearing the completion of his graduate studies at ETH Zurich in early 2023. He was working with his collaborator, Jakub Tětek, who was a PhD student at the University of Copenhagen at the time, to come up with fresh ideas after finishing a paper on moving beyond worst-case analysis in a different setting.
Rozhoň proposed that they attempt to develop an algorithm for the single-source shortest-paths issue that is universally optimum.
“No,” Tětek recalled, “but that’s not possible; that just cannot be done.” However, Rozhoň persuaded him to try. Richard Hladík, a graduate student at ETH Zurich, joined the team in the spring. Rozhoň and Tětek had known him when they were all in high school in the Czech Republic.
After experimenting with a variety of Dijkstra’s algorithm and heap, the three were able to scrounge together a form that was universally optimum. However, they were unable to identify the precise criteria required for universal optimality due to the complexity of the resultant algorithm. This was insufficient in a subject that depends on thorough and exacting evidence.
From mathematical networks, the three students would switch to social networks. While visiting colleagues in New York, Rozhoň and Haeupler had started talking about the issue. After that, Haeupler took a plane to Panama for a vacation, but he wasn’t quite prepared to put the issue behind him.