We consider shortest paths on a realistic multi-modal transportation network where restrictions or preferences on the use of certain modes of transportation or types of roads arise. The regular language constraint shortest path problem deals with this kind of problem. It models constraints by using regular languages. The problem can be solved efficiently by using a generalization of Dijkstra's algorithm (D_(RegLC))- In this paper we present a new label correcting algorithm (lcSDALT) with a speed-up, in our setting, of a factor 3 to 30 in respect to D_(RegLC) and up to a factor 2 in respect to a similar algorithm.
展开▼
