时间依赖网络中非FIFO弧的转化研究

被引：2

作者：

余伟辉

陈闳中

机构：

[1] 同济大学计算机科学与技术系

来源：

小型微型计算机系统 | 2009年 / 30卷 / 01期

关键词：

最短路; 时间依赖网络; 非FIFO弧; 算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

经典最短路算法不能有效地解决时间依赖网络的最短路问题.时间依赖网络中的非FIFO弧的存在是导致经典的最短路算法失效的原因.本文对非FIFO弧的权函数为非连续(存在有限个非连续点)或者离散情况下转化为FIFO弧进行了研究,在允许等待的前提条件下,提出了解决此类问题的方法.建立在经典Dijkstra算法基础上,本文提出了时间依赖网络最短路算法.

引用

页码：156 / 158

页数：3