带多重选择的最短路问题:复杂性和算法

摘要：

本文提出了带多重选择的最短路问题,建立了该问题的数学模型.利用背包问题的一个变形问题--带限制选择的背包问题,证明了该问题是NP-C的.最后利用动态规划给出了一个伪多项式算法,其时间复杂性O(Chmn),其中h是最大的选择重数.

关键词：多重选择、最短路、算法、NP-C

所属期刊栏目：20

分类号：O124(初等数学)

资助基金：国家重点基础研究发展计划973计划

在线出版日期：2004-07-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：300-304