Chinese computer scientists have solved a 40-year-old mathematics bottleneck, an advance that might help boost performance in hi-tech areas ranging from chip design and telecommunications to drone navigation.
One of the most fundamental problems in theoretical computer science is finding the shortest or most efficient path from one starting point to every other point in a network. This problem is known as the “single-source shortest-paths” problem (SSSP).
For decades, the most famous and reliable method to overcome this has been Dijkstra’s algorithm, which repeatedly searches for the shortest path for each segment, continuously comparing and sorting the points until reaching its destination. Yet this sorting step has an unavoidable speed limit.
A new approach devised by a group of young Chinese scientists promises to overcome the barrier, by skipping the sorting process and focusing only on the shortest distance between the most important points, thus greatly reducing calculation time.
The study, led by associate professor Duan Ran’s research team at the Institute for Interdisciplinary Information Sciences (IIIS) at Tsinghua University, was published last month on arXiv, an open-access platform for preprint papers that are yet to be peer reviewed.
This development also won the Best Paper Award at the ACM Symposium on Theory of Computing or STOC, held in Prague in June.
The key to the “single-source shortest-paths” or SSSP problem breakthrough is a combination of Dijkstra’s algorithm with the Bellman-Ford algorithm. Photo: Shutterstock