| 带权区间图的最短路算法 |
| |
| 引用本文： | 王晓东,吴英杰.带权区间图的最短路算法[J].小型微型计算机系统,2003,24(9):1655-1657. |
| |
| 作者姓名： | 王晓东 吴英杰 |
| |
| 作者单位： | 福州大学,计算机科学与技术系,福建,福州,350002 |
| |
| 基金项目： | 国家自然科学基金项目 (60 172 0 17)资助，福建省科技厅杰出人才基金项目 (2 0 0 0 Z14 8)资助 |
| |
| 摘 要： | 提出一个解带权区间图的最短路问题的O(nα(n))时间新算法，其中n是带权区间图中带权区间的个数，α(n)是单变量Ackerman函数的逆函数，它是一个增长速度比log n慢得多的函数，对于通常所见到的n，α(n)≤4．本文提出的新算法不仅在时间复杂性上比直接用Dijkstra算法解带权区间图的最短路问题有较大改进，而且算法设计思想简单，易于理解和实现．
|
| 关 键 词： | 最短路 区间图 并查集 |
| 文章编号： | 1000-1220(2003)09-1655-03 |
A New Algorithm for Shortest Paths on Weighted Interval Graphs |
| |
| WANG Xiao-dong,WU Ying-jie.A New Algorithm for Shortest Paths on Weighted Interval Graphs[J].Mini-micro Systems,2003,24(9):1655-1657. |
| |
| Authors: | WANG Xiao-dong WU Ying-jie |
| |
| Abstract: | |
| |
| Keywords: | shortest paths interval graphs union find algorithms |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
