Shortest path in planar graph and air route network
Pascal Brisset · 2005
This article presents a solution developed in order to create a European air route network. It also shows the improvements made on it. Starting from a very simple route network, the authors optimise it using algorithms based on a simulated annealing algorithm and the Floyd-Warshall shortest path algorithm. In order to improve the performance, a new method which allows to maintain shortest paths is then presented, first through using invariants and then a specific algorithm. If results from general examples indicate a large improvement of the algorithm, the use of it in the application considered here is not as promising.