MLD

3 November 2013

Dijkstra's algorithm (pronounced Deikstra), published in 1959, is a classic method for finding the shortest path in a graph. It works on any graph with non-negative edge weights. Applied to the street network (where “nodes” are crossings, “edges” are roads in between, and “weights” of an edge is the travel time along it) it is unpractically slow. The problem is that if one is looking for the fastest path from Karlsruhe to Berlin (about six hours), the algorithm must go through all the places that one can reach from Karlsruhe in less than six hours. This means, at some point it will be searching in some residential neighbourhood of Paris, Milan or Amsterdam for a secret tunnel that one can use to get to Berlin in less than an hour. This sounds stupid, but after all the algorithm must be able to handle graphs where such situations are possible.

By considering certain properties of the street network, there are many ways to speed up the search (we're talking about making it several million times faster). Usually the idea is to precompute some data and then use it to answer queries faster. One of the methods to achieve this is called MLD, which stands for Multi-Level Dijkstra. The graph is partitioned in regions, for example, in countries. When searching for the shortest path between two given points, one first finds the shortest paths from the origin to all border crossings of the country of origin, then from all border crossings of the destination country to the actual destination, and thus the search is reduced to the graph that consists only of all border crossings and the precomputed paths between them, which is small and the path can be found quickly. This can be done at multiple levels, e.g. each country can be divided in districts and so on. I give the country borders as an easy to understand exapmle, but they are not necessarily useful for partitioning. Ideally, there should be few links between different partitions, and the partitions should be approximately of equal size — country borders may or may not satisfy these criteria.

As a part of my diploma thesis I have to modify an exisiting MLD-implmentation to enable it to accomplish an additional task as well as searching for the shortest path. The code is quite complex and I've been stuck with this for months. I'm gradually getting discouraged and enraged... some strange and nasty mixed feeling...