摘要： 针对含有n个区间的区间图K-连接最短路径(K-SP)问题，提出一种求解区间图K-SP问题的在线算法。分析区间图及其最短路径问题的特有性质，利用改进的动态规划算法和贪心算法，优化在线算法的时间复杂度。理论分析结果表明，该算法的时间复杂度为O(nK+nlgn)，与目前已知最优的离线算法复杂度相同。
关键词:
区间图,
最短路径问题,
K-连接最短路径问题,
贪心算法,
在线算法
Abstract: Aiming at K-link Shortest Path(K-SP) problem on n intervals, this paper presents the on-line algorithm for K-SP problem on interval graphs. It studies the properties about interval graphs and the shortest path problem on interval graphs, is based on the intuition of dynamic programming and greedy algorithms to optimize on-line algorithm complexity. Theoretical analysis result shows the complexity of this algorithms is O(nK+nlgn), same as the best off-line algorithm for this problem.
Key words:
interval graph,
shortest path problem,
K-link Shortest Path(K-SP) problem,
greedy algorithm,
on-line algorithm
中图分类号:
徐云峰, Rudolf Fleischer. 求解区间图K-连接最短路径问题的在线算法[J]. 计算机工程, 2012, 38(11): 51-52,55.
XU Yun-Feng, Rudolf Fleischer. On-line Algorithm for K-link Shortest Path Problem on Interval Graph[J]. Computer Engineering, 2012, 38(11): 51-52,55.