带权区间图的最短路算法

A New Algorithm for Shortest Paths on Weighted Interval Graphs

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

This paper presents a new O(nα(n)) time algorithm for computing single source shortest paths in a weighted interval graph, where n is the number of weighted intervals. α(n) is the functional inverse of Ackermann's function. Its growing rate is much slower than that of function logn. For commonly used n , α(n)≤4. The new algorithm is not only an improvement in time complexity compared to the algorithm using Dijkstra algorithm directly, but also simple and easy to implement.