关键词: 随机Dijkstra算法, 动态路径诱导系统, 最短路径, 遗传算法

Abstract:

An algorithm based on random Dijkstra algorithm and applying genetic algorithm to solve SPDRGS(Shortest Path problem on Dynamic Route Guidance System) was proposed. By applying random Dijkstra algorithm, the algorithm cleared out the biggest obstruction between the genetic algorithm and SPDRGS, which is how to get the initial generation of GA(Genetic algorithm). According to DRGS’s (Dynamic Route Guidance System) demand for time complexity and network constraint condition of route guidance algorithms, this algorithm can quickly find the excellent path and does not need any network constraint condition, which also can solve the problems on continuously and discrete dynamic networks. So the algorithm proposed can satisfy the demand of DRGS.

Key words: random Dijkstra algorithm, DRGS, shortest path, genetic algorithm