| 带限制条件的多权最短路径近似算法 |
| |
| 引用本文： | 戴树贵,孙强,潘荫荣.带限制条件的多权最短路径近似算法[J].计算机工程,2003,29(7):88-91. |
| |
| 作者姓名： | 戴树贵 孙强 潘荫荣 |
| |
| 作者单位： | 华东师范大学计算机科学系,上海,200062 |
| |
| 摘 要： | 带限制条件的多权最短路径问题具有广泛的用途。该文针对有向图，给出了一个带一个限制条件的多权最短路径的近似算法并且分析了它的时间复杂度。
|
| 关 键 词： | 最短路径 权 评价函数 时间复杂度 空间复杂度 |
| 文章编号： | 1000-3428(2003)07-0088-04 |
| 修稿时间： | 2002年7月9日 |
Approximate Algorithm for the Multiple Weights Shortest-path Problem with a Restriction |
| |
| DAI Shugui,SUN Qiang,PAN Yinrong.Approximate Algorithm for the Multiple Weights Shortest-path Problem with a Restriction[J].Computer Engineering,2003,29(7):88-91. |
| |
| Authors: | DAI Shugui SUN Qiang PAN Yinrong |
| |
| Abstract: | 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. |
| |
| Keywords: | Shortest path Weight Value function Time complexity Space complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
