带权区间图的最短路算法

摘要：

提出一个解带权区间图的最短路问题的O(nα(n))时间新算法,其中n是带权区间图中带权区间的个数,α(n)是单变量Ackerman函数的逆函数,它是一个增长速度比log n慢得多的函数,对于通常所见到的n,α(n)≤4.本文提出的新算法不仅在时间复杂性上比直接用Dijkstra算法解带权区间图的最短路问题有较大改进,而且算法设计思想简单,易于理解和实现.

关键词：最短路、区间图、并查集

所属期刊栏目：24

分类号：TP30(计算技术、计算机技术)

资助基金：国家自然科学基金60172017;福建省科技厅杰出人才基金2000Z148

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

页数：共3页

页码：1655-1657