利用最小填充树分解方法实现最短路径查询

随着社会的快速发展,道路网的规模越来越大,传统的最短路径算法已不能满足当前的实时要求,本文将基于最小度的树分解查询算法扩展至有向有权图中,提出了效果更好的基于最小填充的树分解最短路径查询算法,并对查询算法求解集合的过程进行了优化,实验结果表明,随着数据规模的增长,算法的时间效率相对于采用二叉堆的Dijkstra算法得到数量级提高。

A Shortest Path Algorithm Based on Tree Decomposition of Min-fill

With the rapid development of society,the scale of the road network is increasing rapidly and the classical algorithms can't satisfy with the real-time demand.According to the query algorithm based on tree decomposition of mindegree,this paper put forward the better one based on tree decomposition of min-fill in the weighted and directed graph,and optimized the process of solving the set in the searching algorithm.The results showed that with the increasing scale of data,the algorithm's time efficiency offered orders-of-magnitude performance improvement over the Dijkstra algorithm based on binary heap.