【摘要】 在实践中,Dijkstra算法是处理道路网络的最有效的算法之一。但Dijkstra算法每次都需要扫描节点集合中的所有节点,降低了算法效率。通过对前人的成果和嵌入式系统的性能进行研究和分析后,分两步来提高算法效率:第1步通过数据的预处理缩小算法的搜索范围;第2步为每个节点添加属性值、增加前趋表,以辅助算法快速找到一条最短路径。然后将此算法应用于嵌入式GIS系统中,并使用大量的数据进行测试,结果表明改进的算法明显提高了GIS系统的效率。更多还原

【Abstract】 Dijkstra algorithm is one of the most valid algorithms in dealing with the real road networks.But it needs to scan nearly all the nodes in the Dijkstra algorithm,which reduces the efficiency.The other people’s achievements and embedded-GIS system’s perform-ance are researched and analyzed.The algorithm’s efficiency is improved by two steps: first,the scanning scale is reduced by data pre-processing;second,property value is added to each node and a priority table,which helps the algorithm to find a shortest path fleetly.The improved algorithm is applied to embedded-GIS system,the efficiency of the GIS system is improved greatly.更多还原