限制性最短路问题  

作　　者：李睿[1] 杨子兰[1] 

机构地区：[1]云南大学旅游文化学院信息与计算机科学系,云南丽江674100

出　　处：《计算机与信息技术》2012年第2期24-26,共3页Computer & Information Technology

摘　　要：给定一个无圈图G及与边关联的长度权重和时间权重,需要寻找G上固定两点之间的关于长度权重的最短路,并且路上关于时间权重的路长不能超过给定的一个正常数。这就是限制性最短路问题。本文给出了限制性最短路问题的几种FPTAS,并对算法的复杂度进行了分析,对算法的一些部分进行改进,最后把算法推广到一类有圈的图上。

关 键 词：限制性最短路 放缩取整法 区间划分法 

分 类 号：O157.5[理学—数学]