关键词: 离散变权网络，动态最短路径，算法

Abstract: 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. hhe experiments also prove that the new algorithm is applicable to dynamic traffic navigation.

Key words: Discrete varying weight, Dynamic shortest path, Algorithm