何建军　王丽芳

摘要摘要：对点带成本的最短路径问题进行了研究。根据点带成本最短路径问题特点，对Dijkstra算法进行修改后给出一个时间复杂度为O（|V|2+|E|）、空间复杂度为O（|V|+|E|）的算法，并在此基础上充分利用问题的特点，给出一个时间复杂度为O（w|V|）、空间复杂度为O（|V|+|E|）、构造所有点带成本最短路径的算法。

关键词关键词：最短路径；点带成本；带权图；最小点成本最短路径

DOIDOI：10.11907/rjdk.1431088

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2015）004007803

0引言

最短路径（SP）问题一直是运筹学、计算机科学、交通运输等领域的研究热点。很多实际问题都可以转化为网络中的最短路径问题，如道路交通网络中的出行路线选取问题、计算机网络中的路由选择问题等。针对网络的最短路径问题研究具有重要的理论和现实意义。早期专家学者研究的算法有Dijkstra算法[1]、Bellman算法[2]、Floyd算法等，现阶段对最短路径算法的研究呈现以下几个特点：①并行化，如文献[4][6]等；②将遗传算法、神经网络、启发式算法等引入最短路径算法设计中，如文献[7][9]等；③对各种约束条件下的最短路径算法进行研究，如文献[10][13]等；④研究最短路径算法的各种优化实现，如文献[14]。

早期文献[10]对点带成本约束的最短路径算法进行了研究，文献[10]首先证明了点带约束成本SP问题是一个NP完全问题，然后用动态规划法给出一个时间复杂度为O（Cmn）的伪多项式时间算法。对最小点成本最短路径问题，文献[10]把主要目标（路径长度最短）的最优解作为次要目标（点成本最小）的约束条件进行求解，需要两次调用Dijkstra算法求最短路径，并且需要构造网络G′=（V，A′，L′），造成一些不必要的时间和空间开销。……