Network Routing by Landmarks
Urs-Jakob Rüetschi, David Caduff, Sabine Timpf, Frank Schulz, Alexander Wolff · 2006
A route in a network can be described as a sequence of nodes. Given a route, travellers need directions to follow it, which are preferably expressed as a sequence of instructions, as for instance, face towards the tower and move along the river. This paper presents a method to find routes in a network with the property that they can be described by a simple sequence of instructions. The key problems that we need to solve are (1) how to attribute landmark information to the network and (2) how to find an optimal route. We approach the first problem by using landmarks as parts of instructions and mapping instructions to sets of edges in the network. The second problem can be solved by building an auxiliary graph such that a standard Dijkstra shortest path algorithm can be used to find optimal routes. Preliminary tests indicate that our approaches produce good results.