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.
Comments are closed.