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