摘要
带限制条件的多权最短路径问题具有广泛的用途。该文针对有向图，给出了一个带一个限制条件的多权最短路径的近似算法并且分析了它的时间复杂度。
The shortest-path problem with restrictions is widely practical. In this paper, along each point that has a directed arc from the source, one path is found subject to the restriction. From all of these paths, the one with the smallest value function is chosen as the optimal path. The time and the space complexity of the algorithm are also discussed.
出处
《计算机工程》
CAS
CSCD
北大核心
2003年第7期88-91,共4页
Computer Engineering
关键词
最短路径
权
评价函数
时间复杂度
空间复杂度
Shortest path
Weight
Value function
Time complexity
Space complexity
