The “single source shortest path problem” is a challenge in algorithms that has been troubling scholars worldwide for more than 50 years. In a network where there may be connections with negative weights, the issue primarily revolves on how to develop a mathematical formula that best discovers the shortest route between a node and all other nodes.
Sounds challenging? Possibly. However, a lot of the tools and technology we rely on to go about already use this kind of calculation, such as Google Maps, which leads us across towns and across landscapes.
Researchers from the Department of Computer Science at the University of Copenhagen have now cracked the code to the single source shortest path issue, a conundrum that has baffled scientists for decades.
“We discovered an algorithm that solves the problem in virtually linear time, the fastest way possible. It is a fundamental algorithmic problem that has been studied since the 1950s and is taught around the world. This was one of the reasons that prompted us to solve it,” explains Associate Professor Christian Wulff-Nilsen, who clearly finds it tough to leave an unsolved algorithmic problem alone.
Quicker calculations for routing electric cars
Wulff-Nilsen made yet another advancement in the same field last year, one that led to a solution for the problem of locating the shortest path in a dynamic network. He builds on previous work in his answer to the most current puzzle.
The researcher believes that resolving the single source shortest path problem may open the door to algorithms that enable electric automobiles to instantly determine the fastest and most energy-efficient route from point A to point B.
We discovered an algorithm that solves the problem in virtually linear time, the fastest way possible. It is a fundamental algorithmic problem that has been studied since the 1950s and is taught around the world. This was one of the reasons that prompted us to solve it.
Associate Professor Christian Wulff-Nilsen
“We’re adding a dimension that previous algorithms don’t have. This dimension lets us look at what we call negative weights. A practical example of this can be with reference to the hills in a road network, which is good to know if you have an electric car that charges while traveling downhill,” explains Wulff-Nilsen.
Facts about the single source shortest path problem
- Finding the shortest routes between a given starting node and every other node in a network is the goal of the single source shortest path issue.
- A graph of the network made up of nodes and the edges that connect them serves as a visual representation of the network.
- Each edge has a weight that reflects how expensive it is to go along that edge and a direction (for example, this might be used to depict one-way roads). A traditional Dijkstra algorithm can almost instantly solve the issue if all edge weights are positive.
- The new result solves the problem in nearly the same amount of time as Dijkstra’s algorithm, but allows for negative edge weights as well.
“In principle, the algorithm could be used to warn actors, such as central banks, if speculators are speculating on buying and selling various currencies. A lot of this happens using computers today. But because our algorithm is so fast, it might be able to be used to detect loopholes before they are exploited,” says Christian Wulff-Nilsen.
The researcher emphasizes that there are already systems in place for figuring out routes and currency for electric cars. But by figuring out the single source shortest path problem, scientists were able to develop an excellent algorithm that is now nearly impossible to outperform in terms of speed. In addition, because of its simplicity, it is simple to adapt to the diverse needs of society.
Honored in the U.S.
The work to solve the problem has not gone unnoticed. Indeed, people around the world seeking to congratulate them and find out more about how they did it have already contacted Christian Wulff-Nilsen and his colleagues.
At the same time, a “best paper award” was given to the study that describes their discovery at the FOCS (Foundation of Computer Science) conference in Denver, Colorado. It is the most esteemed conference in theoretical computer science after the STOC. The FOCS conference ran from 31 October to 3 November 2022.
“People from around the world attend this conference to see the best results being presented,” says Christian Wulff-Nilsen.
The research was conducted in a collaboration between Christian Wulff-Nilsen, from the Department of Computer Science, Danupon Nanongkai of the Max Planck Institute and their American colleague, Aaron Bernstein from Rutgers University.
