带权区间图的最短路算法

来源 :小型微型计算机系统 | 被引量 : 0次 | 上传用户：liongliong589

【摘要】

：

提出一个解带权区间图的最短路问题的O(nα(n))时间新算法,其中n是带权区间图中带权区间的个数,α(n)是单变量Ackerman函数的逆函数,它是一个增长速度比log n慢得多的函数,对

【作者】

：

王晓东吴英杰

【机构】

：

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

【出处】

：

小型微型计算机系统

【发表日期】

：

2003年9期

【关键词】

：

最短路区间图并查集 shortest paths interval graphs union find algorithms

【基金项目】

：

国家自然科学基金，福建省科技厅杰出人才基金

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

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

其他文献

本科实习护生对临床教师信任度的调查分析

目的了解本科护生的信任度及实习期间对临床教师的信任度情况，为进一步提高教学质量提供依据。方法采用人际信任量表（ITS）和自制信任度临床带教相关影响因素问卷，对在上海市7所医

期刊

实习本科护生临床教师人际信任

北京延庆地区蜂业发展前景分析

延庆县位于北京西北部，三面环山，一面临水，属大陆性季风气候区，年平均气温8．8℃，林木资源非常丰富，有林地面积15万公顷，林木覆盖率达到60％，植被属暖温带针阔混交过渡带，有刺槐、荆条、山

期刊

延庆县养蜂业发展前景北京蜜源植物季风气候区年平均气温林木覆盖率

肝硬化患者血清甲状腺激素的变化

为观察肝硬化患者血清甲状腺激素的变化,我们用放射免疫法(RIA)检测40例肝硬化患者的血清T3、T4、TSH和rT3并以30例健康成人作对照.结果:肝硬化组血清T3为0.92nmol±0.24

期刊

肝硬化血清甲状腺激素放射免疫法肝功能

利用巢门扩缩调整蜂群饲料过剩与短缺

笔者春繁时采用扩缩蜂箱巢门来降低管理难度，合理利用强群外勤蜂来调整蜂群饲料，取得满意的效果，具体办法介绍如下：

期刊

蜂群饲料调整扩缩巢门短缺合理利用蜂箱

病区护士方位板的制作与应用

护理人力资源不足是普遍存在的问题,尤其是节假日、中午班及夜班时。由于值班人数少,当护士进入病房执行治疗护理操作时,病区其他患者、家属及医护人员有事找不到护士,而医院

期刊

护理人力资源护士方位板

带权区间图的最短路算法

其他学术论文