A New Shortest Path Algorithm based on Heuristic Strategy

The paper presents a new dynamic direction restricted algorithm based on the Dijkstra algorithm, direction restricted algorithm and area restricted algorithm for computing shortestpath from one node to another node in traffic networks. This new algorithm can be combined with many other used heuristic algorithms. This new algorithm has been implemented in practice. The implementation performance of that new algorithm is compared to the Dijkstra algorithm, the A*algorithm, and so on. The results of comparison show that the new algorithm is efficient not only by itself but also by combining with other algorithms. For a network containing 5000 nodes and 10000 arcs, the dynamic direction restricted algorithm led to almost a saving ratio of 50 in terms of both number of nodes selected and computation times, compared with the Dijkstra algorithm.