Researchers develop a way to solve the single source shortest path problem using non-negative edge weights(connection between nodes shown in a network graph).
Networking plays an important role in today’s world. From defense to general communication, each community vertical is linked to each other through an interconnected network. As the network develops and expands, the problem of finding the shortest path of communication in that network arises. This has been a great concern in networking since the 1950s.
Researchers at the University of Copenhagen’s Department of Computer Science have developed a solution to this shortest path problem. “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.
The single source shortest path algorithm aims 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. Christian Wulff-Nilsen says, “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.”
Researchers claim that solving the single source shortest path algorithm can allow researchers to create a superb algorithm that is 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.
References : Aaron Bernstein et al, Negative-Weight Single-Source Shortest Paths in Near-linear Time, arXiv (2022). DOI: 10.48550/arxiv.2203.03456
