Fast Algorithm of Dynamic Shortest Paths Based on Discrete Varying-weight Networks
Zhaohui Zhang · 2010
In discrete varying-weight networks,the computational complexity of the optimal algorithms for shortest paths is far more than O(n2) and they are not suitable for dynamic traffic navigation systems.This paper presented a fast algorithm of dynamic shortest path for discrete varying weight networks.It does't select a candidate vertex as the next current one and makes a minimal sum from the current vertex to the candidate one and from it to the destination one until the current vertex is the destination.The new algorithm yields a sub-optimal solution of the shortest path,but it is more effective than the optimal algorithm and its solution is better than the dynamic solution of the shortest distance path.The experiments also prove that the new algorithm is applicable to dynamic traffic navigation.