Solution to the shortest path problem

November 15 () –

Researchers at the University of Copenhagen have succeeded in solving the shortest path problem for a single source, a riddle that has stumped experts for decades.

Solve the riddle”can reduce battery consumption of electric cars and make life more difficult for currency speculators in the future,” reports the university it’s a statement.

“We discovered an algorithm that solves the problem in nearly linear time, in the fastest way possible. It is a fundamental algorithmic problem that has been studied since the 1950s and is taught worldwide.. This was one of the reasons that prompted us to solve it,” explains Associate Professor Christian Wulff-Nilsen.

The goal of the single source shortest path problem is find the shortest paths from a given starting node to all other nodes in a network.

Shortest path algorithms allow studying different path costs, such as distance, travel time, generalized cost, etc. This type of calculation is already used in a wide range of applications and technologies that we depend on for orientation, how Google Maps guides us through landscapes and citiesfor instance.

Last year, Wulff-Nilsen made another breakthrough in the same area, producing a result addressing how to find the shortest path in a network that changes over time. His solution to the recent puzzle is based on that work.

The researcher believes 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 to do so in the most efficient way from an energy point of view.

“We are adding a dimension that previous algorithms do not have. This dimension allows us to see what we call negative weights. A practical example of this can be with reference to hills in a road networkwhich is good to know if you have an electric car that charges while traveling downhill,” Wulff-Nilsen explains.

In the single source shortest path problem, the network is represented as a graph made up 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, which expresses how expensive it is to travel along that edge. If all edge weights are nonnegative, the problem can be solved in nearly linear time with a classical Dijkstra algorithm, which aims to find the path from the minimum length of a source vertex to the rest of the vertices of the graph

The new result solves the problem in almost the same amount of time as Dijkstra’s algorithm, but it also allows negative edge weights.

“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 points out that there are already systems for calculating both currency and routes for electric cars. But solving the single source shortest path problem has allowed researchers creating an excellent algorithm that becomes almost impossible to beat when it comes to speed. At the same time, its simplicity makes it easy to adopt for the various needs of society.

The research is currently available on arXiv.