利用组合技术的迪杰斯特拉算法改进探讨

Optimal Dijkstra arithmetic for shortest path based on composite technology

最短路径分析是物流配送最基本的网络分析,等价于图论中的结点间求解最短路径的问题。本文在研究迪杰斯特拉算法基础上,基于组合技术对该算法进行改进。首先利用图的节点——弧段联合结构;其次搜索方法改为双向搜索;最后对扫描点按其所在边的权值进行排列。实验表明改进算法运行效率较高。

Shortest path is the most basic network analysis in logistics distribution, equivalent to the shortest path of diredoed graph in Graph Theory. The paper proposed an improved of Dijkstra based on a composite technology, Firstly, it used graph node-arc joint structure; secondly, bi-directional search method was chosen; finally, according to the edge weights the scanning points were ranked. Experiments showed that the improved Dijkstra would be efficient.