Finding the shortest route from an origin to a destination is the primary concern for any traveller. When heading somewhere new, most of us leave it to computer algorithms to help us find the best route, whether by using a car's GPS, or public transport and map apps on their phone. Still, there are times when a proposed route doesn't quite align with reality. This is because road networks, public transportation networks and other networks aren't static. The best route can suddenly be the slowest, e.g. because a queue has formed due to roadworks or an accident.
For 40 years, an algorithm has been sought to provide an optimal solution to this problem. Now, computer scientist Christian Wulff-Nilsen of the University of Copenhagen and two research colleagues have come up with a recipe.
One of the most classic algorithmic problems deals with calculating the shortest path between two points. A more complicated variant of the problem is when the route traverses a changing network— whether this be a road network or the internet. People probably don't think about the complicated math behind routing suggestions in these types of situations. The software being used is trying to solve a variant for the classic algorithmic "shortest path" problem, the shortest path in a dynamic network. For 40 years, researchers have been working to find an algorithm that can optimally solve this mathematical conundrum. Now, Christian Wulff-Nilsen of the University of Copenhagen's Department of Computer Science has succeeded in cracking the nut along with two colleagues.
"We have developed an algorithm, for which we now have mathematical proof, that it is better than every other algorithm up to now—and the closest thing to optimal that will ever be, even if we look 1000 years into the future," says Associate Professor Wulff-Nilsen.
Optimally, in this context, refers to an algorithm that spends as little time and as little computer memory as possible to calculate the best route in a given network. This is not just true of road and transportation networks, but also the internet or any other type of network.
Traditional algorithms assume that a graph is static, which is rarely true in the real world. When these kinds of algorithms are used in a dynamic network, they need to be rerun every time a small change occurs in the graph—which wastes time.
The researchers represent a network as a so-called dynamic graph. In this context, a graph is an abstract representation of a network consisting of edges, roads for example, and nodes, representing intersections, for example. When a graph is dynamic, it means that it can change over time. The new algorithm handles changes consisting of deleted edges—for example, if the equivalent of a stretch of a road suddenly becomes inaccessible due to roadworks.
"The tremendous advantage of seeing a network as an abstract graph is that it can be used to represent any type of network. It could be the internet, where you want to send data via as short a route as possible, a human brain or the network of friendship relations on Facebook. This makes graph algorithms applicable in a wide variety of contexts," explains Christian Wulff-Nilsen.