Practical algorithm for shortest path on transportation network

The shortest path problem is to find a path between two vertices (nodes) on a given graph, such that the sum of the weights on its constituent edges is minimized. This problem has been intensively investigated over years, due to its extensive applications in graph theory, artificial intelligence, computer network and the design of transportation systems. The classic Dijkstra's algorithm was designed to solve the single-source shortest path problem for a static graph. It works starting from the source node and calculating the shortest path on the whole network. Noting that an upper bound of the distance between two nodes can be evaluated in advance on the given transportation network, we proposes a practical algorithm in this paper to calculate the shortest path. The proposed algorithm works on a sub-graph limited by the given upper bound of the distance between the two nodes, rather than on the whole network as did in Dijkstra's algorithm. Experimental results on real dataset with 150 nodes and 176 edges, which is a subnet of the road-map in the Maryland State in US, show that the proposed algorithm reduce the calculations by about 8% on average in comparison to the traditional Dijkstra's algorithm.

I. Introduction

With the development of geographic information systems (GIS) technology, GIS offers many network and transportation related analysis functions in different kinds of navigation systems, monitor and other aided systems [1]. Among them a key problem is computing the shortest paths between different locations. In earlier work, Dijkstra's algorithm (DA) [2] was a classic algorithm designed to solve the single-source shortest path problem for a static graph with non-negative weights. Then, based on DA, many algorithms are researched over years. In Cherkassky, Goldberg and Radzik's experiment [3], a large number of algorithms were tested along with several proposed refinements. It is one of the most comprehensive evaluations of the shortest path algorithms to date. All codes in their experiments were made available as open source. Using the open source codes, F. Benjamin Zhan conducted an evaluation on a variety of real road network [4]. There are three algorithms suggested as the three fastest shortest path algorithms: TWO-Q, DIKBD and DIKBA. JinFU Leng developed the TWO-Q by introducing a minlabel variable [4][5]. algorithm [6] extends DA's single-source shortest path algorithm, by cutting down on the size of the sub-graph that must be explored, if additional information, such as a lower bound on the distance to the target, is available.