带权区间图的最短路算法

被引：3

作者：

王晓东

吴英杰

机构：

[1] 福州大学计算机科学与技术系

[2] 福州大学计算机科学与技术系福建福州

[3] 福建福州

来源：

小型微型计算机系统 | 2003年 / 09期

关键词：

最短路; 区间图; 并查集;

D O I：

暂无

中图分类号：

TP311.12 [];

学科分类号：

081202 ; 0835 ;

摘要：

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

引用

页码：1655 / 1657

页数：3

共 4 条

[1]

Algorithmic graph theory and perfect graphs〔M〕. Golumbic M C. . 1980

[2]

Efficient algorithms for interval graphs and circular arc graphs 〔M〕. Gupta U I,Lee D T and Leung J Y T. Networks . 1982

[3]

Testing for the consecutive ones property, interval graphs, and graph planarity using PQ tree algorithms 〔J 〕. Booth K S and Lueker G S. Journal of Computer and System Sciences . 1976

[4]

A class of algorithms which require nonlinear time to maintain disjoint sets 〔J 〕. Tarjan R E. Journal of Computer and System Sciences . 1979

← 1 →