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

【Abstract】 In this paper,we put forward the concept of shortest path problem with multiple choice and give the formulation of this problem.By using a variation of (KP),it is proved that this problem is NP hard.Lastly,a psedopolynomial algorithm is given.更多还原