(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.
“We discovered an algorithm that solves the problem in virtually linear time, the fastest way possible,” explains associate professor Christian Wulff-Nilsen. “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.”
Last year, Wulff-Nilsen made a breakthrough in the same area, one that produced a result that 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,” says 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 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 an algorithm that becomes almost impossible to beat in speed. At the same time, its simplicity makes it easy to adopt for the various needs of society.
The research article that details their discovery has been honoured with a “best paper award” at the FOCS (Foundation of Computer Science) conference in Denver, Colorado.
https://techxplore.com/news/2022-11-scientists-succeed-algorithmic-riddle-1950s.html
