NOVEMBER 14, 2022 by University of Copenhagen
For more than half a century, researchers around the world have been struggling with an algorithmic problem known as “the single source shortest path problem.” The problem is essentially about how to devise a mathematical recipe that best finds the shortest route between a node and all other nodes in a network, where there may be connections with negative weights.
Sound complicated? Possibly. But in fact, this type of calculation is already used in a wide range of the apps and technologies that we depend upon for finding our ways around—as Google Maps guides us across landscapes and through cities, for example.
Now, researchers from the University of Copenhagen’s Department of Computer Science have succeeded in solving the single source shortest path problem, a riddle that has stumped researchers and experts 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
Last year, Wulff-Nilsen made another breakthrough in the same area, one that produced a result which addressed how to find the shortest path in a network that changes over time. His solution to the recent riddle builds upon that work.
The researcher thinks that solving the single source shortest path problem could pave the way for algorithms that not only help electric cars calculate the fastest route from A to B in an instant, but do so in the most energy-efficient manner.
“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
- The aim of the single source shortest path problem is to find the shortest paths from a given starting node to all other nodes in a network.
- The network is represented as a graph consisting of nodes and connections between them, called edges.
- Each edge has a direction (for example, this can be used to represent one-way roads), as well as a weight, that expresses how expensive it is to travel along that edge. If all edge weights are non-negative, the problem can be solved in virtually linear time with a classical Dijkstra algorithm.
- 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 systems for calculating both currency and routes for electric cars already exist. But solving the single source shortest path problem has allowed researchers to create a superb algorithm that becomes almost impossible to beat with regards to speed. At the same time, its simplicity makes it easy to adopt for the various needs of society.
Honored in the U.S.
The work to solve the problem has not gone unnoticed. Indeed, Christian Wulff-Nilsen and his colleagues have already been contacted by people around the world seeking to congratulate them and find out more about how they did it.
At the same time, the research article which details their discovery has been honored with a “best paper award” at the FOCS (Foundation of Computer Science) conference in Denver, Colorado.
“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.
The research is currently available on arXiv.
More information: Aaron Bernstein et al, Negative-Weight Single-Source Shortest Paths in Near-linear Time, arXiv (2022). DOI: 10.48550/arxiv.2203.03456
Journal information: arXiv
Provided by University of Copenhagen
Leave a Reply