Improvement of a Shortest Routes Algorithm
Nicolas Lassabe, Alain Berro, Yves Duthen · 2007
This article describes an original shortest path algorithm for graphs representing a real road network. We test the influence of a coefficient weighing the evaluated distance used in such short path algorithms. This coefficient has an influence on the performance of the shortest path algorithm which uses the evaluated distance as heuristic. We try to provide a better algorithm using this heuristic and we test its evaluation in various situations. The results presented in this paper are used to write new shortest path algorithms for large real road networks. To conclude, we experiment this algorithm and some alternatives in various situations.