基于平面图的改进Dijkstra算法研究

Research on Improved Dijkstra Algorithm Based on Ichnography

针对在平面图应用条件下,对应用Dijkstra算法进行最短路径搜索的设计方法和运算过程进行分析,从应用的角度,改进Dijkstra算法,设计一种新的数据存储结构,并建立简洁的估价函数,使基于平面图的动态最短路径规划算法在时间复杂性和空间复杂性均达到线性。

Concerning with the computation of the shortest paths over a network of an ichnography by Dijk-stra algorithm, the design method and process computation are analyzed. From the view of application, the Di-jkstra method is reformed through a new data structure and a simple evaluation function. This algorithm reaches a linear time and space dependence in searching for the shortest paths in a real network of ichnography.