| 点带约束成本的最短路问题 |
| |
| 引用本文： | 李帮义,何勇,姚恩瑜.点带约束成本的最短路问题[J].高校应用数学学报(A辑),2000,15(1):93-96. |
| |
| 作者姓名： | 李帮义 何勇 姚恩瑜 |
| |
| 作者单位： | 浙江大学应用数学系,杭州,310027 |
| |
| 基金项目： | 中国科学院资助项目，国家重点基础研究发展计划(973计划)，19701028，，， |
| |
| 摘 要： | 本文提出了点带约束成本的最短路问题，证明了该问题是ＮＰ－完全的，并利用动态规划给出了一个伪多项式算法，对所有顶点约束成本相同的情况，给出了一个时间复杂性为Ｏ（ｍｎ＾２）的算法，对最小点成本最短路问题，给出了一个时间复杂性为Ｏ（ｎ＾２）的算法。
|
| 关 键 词： | 最短路问题 计算复杂性 点带约束成本 有向网络 |
SHORTEST PATH PROBLEM WITH CONSTRAINTS OF NODE'S COST |
| |
| Li Bangyi,He Yong,Yao Enyu.SHORTEST PATH PROBLEM WITH CONSTRAINTS OF NODE'S COST[J].Applied Mathematics A Journal of Chinese Universities,2000,15(1):93-96. |
| |
| Authors: | Li Bangyi He Yong Yao Enyu |
| |
| Abstract: | The shortest path problem with constraints of node's cost is put forward, and it is proven to be NP\|Complete.Then using dynamic programming, a pseudopolynomial\|time algorithm is given. Lastly for a special case, an algorithm is given with the time complexity O(mn\ 2) . |
| |
| Keywords: | The Shortest Path Complexity Algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
