Implementation of Route Selection Function Based on Improved Floyd Algorithm

摘要

The improved Floyd algorithm is presented in order to solve the problem of high computational complexity when the shortest path of a large number of nodes in urban road network is computed using traditional Floyd algorithm. And the function of route selection based on the improved Floyd algorithm is realized by simulation. In the algorithm, firstly, the various nodes will be compared and the nodes that have nothing to do with the results are removed, and the iteration matrix and the serial number matrix for computing shortest path the were constructed. Experimental results showed that the computational complexity of the improved Floyd algorithm was reduced by half compared with the original algorithm. And the shortest path can be simply, intuitively and efficiently found through checking iteration matrix and serial number matrix.