点带约束成本的最短路问题

被引：8

作者：

李帮义

何勇

姚恩瑜

机构：

[1] 浙江大学应用数学系!杭州

来源：

高校应用数学学报A辑(中文版) | 2000年 / 01期

关键词：

最短路问题; 计算复杂性; 算法;

D O I：

10.13299/j.cnki.amjcu.000880

中图分类号：

O224 [最优化的数学理论];

学科分类号：

摘要：

本文提出了点带约束成本的最短路问题．证明了该问题是ＮＰ－完全的，并利用动态规划给出了一个伪多项式算法．对所有顶点约束成本相同的情况，给出了一个时间复杂性为Ｏ（ｍｎ２）的算法．对最小点成本最短路问题，给出了一个时间复杂性为Ｏ（ｎ２）的算法．

引用

收藏

页码：93 / 96

页数：4

相关论文

共 3 条

[1]

Time-varying shortest path problem with constraints. Gai,X. Networks . 1997

[2]

A dual algorithm for the constrained shortest path. Handier,G. Networks . 1980

[3]

A dual programming algorithm for the shortest path problem. Loachim,I. Networks . 1998