Computer scientists succeed in solving algorithmic riddle from the 1950s – Tech Xplore
Click here to sign in with or
Forget Password?
Learn more
share this!
243
21
Share
Email
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
“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.
Explore further
Facebook
Twitter
Email
Feedback to editors
3 hours ago
0
Nov 14, 2022
0
Nov 14, 2022
0
Nov 11, 2022
0
Nov 11, 2022
1
19 minutes ago
24 minutes ago
1 hour ago
2 hours ago
3 hours ago
3 hours ago
9 hours ago
19 hours ago
20 hours ago
Nov 14, 2022
Mar 11, 2021
Apr 12, 2021
Aug 17, 2020
Apr 03, 2019
Aug 26, 2020
Aug 05, 2019
3 hours ago
3 hours ago
Nov 11, 2022
Nov 10, 2022
Nov 10, 2022
Nov 10, 2022
Use this form if you have come across a typo, inaccuracy or would like to send an edit request for the content on this page. For general inquiries, please use our contact form. For general feedback, use the public comments section below (please adhere to guidelines).
Please select the most appropriate category to facilitate processing of your request
Thank you for taking time to provide your feedback to the editors.
Your feedback is important to us. However, we do not guarantee individual replies due to the high volume of messages.
Your email address is used only to let the recipient know who sent the email. Neither your address nor the recipient’s address will be used for any other purpose. The information you enter will appear in your e-mail message and is not retained by Tech Xplore in any form.
Daily science news on research developments and the latest scientific innovations
Medical research advances and health news
The most comprehensive sci-tech news coverage on the web
This site uses cookies to assist with navigation, analyse your use of our services, collect data for ads personalisation and provide content from third parties. By using our site, you acknowledge that you have read and understand our Privacy Policy and Terms of Use.