%0 Journal Article %A 徐云峰 %A Rudolf Fleischer %T 求解区间图K-连接最短路径问题的在线算法 %D 2012 %R 10.3969/j.issn.1000-3428.2012.11.016 %J 计算机工程 %P 51-52,55 %V 38 %N 11 %X 针对含有n个区间的区间图K-连接最短路径(K-SP)问题,提出一种求解区间图K-SP问题的在线算法。分析区间图及其最短路径问题的特有性质,利用改进的动态规划算法和贪心算法,优化在线算法的时间复杂度。理论分析结果表明,该算法的时间复杂度为O(nK+nlgn),与目前已知最优的离线算法复杂度相同。 %U http://www.ecice06.com/CN/10.3969/j.issn.1000-3428.2012.11.016