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

摘要：

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

关键词：图的树分解、最小填充、最小度、最短路径

所属期刊栏目：23

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金项目41471383

在线出版日期：2017-04-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：68-72