基于Dijkstra算法过必经点的最短路径设计

Design of the shortest path of passing the necessary points based on Dijkstra algorithm

为改善传统诱导系统只涉及无必经点的单条最短路径的实现、使出行者的选择受到一定限制的局限性,设计了一种过必经点的最短路径,可方便人们的出行。通过建立路网节点属性数据库保存相关节点信息,并将路网信息数据导入到数据库,完善路网结构信息,再通过嵌入Dijkstra算法查找出过K个必经点的N条最短路径,最后将相关的路径信息显示在界面上。以26节点数据集模拟道路情况,实验结果表明该算法可以保证理论上的过K(小于5)个必经点的前N(小于5)条最短路径的实现,有效扩充了最短路径的数量,满足用户选择需求。

The traditional guidance system only involves the realization of a single shortest path without a necessary point,which limits the choice of the traveler.For this purpose,a shortest path is designed to improve the limitation and facilitate people’s travel.The relevant node information is saved by establishing the road network node attribute database,and the road network information data is imported into the database,and the road network structure information is improved.Then,by embedding the Dijkstra algorithm,the N shortest paths of the K necessary points are found.Finally,the relevant path information is displayed on the interface.By experimenting with the 26-node dataset to simulate the road condition,we get the experimental results that the algorithm can guarantee the realization of the former N(N less than 5)shortest paths of the K(K less than 5)necessary points.It effectively expands the number of shortest paths,and meet the user’s choice needs.