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

SHORTEST PATH PROBLEM WITH CONSTRAINTS OF NODE'S COST

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

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) .