| 基于不含负长度环有向图的Dijkstra算法 |
| |
| 引用本文： | 尹方,邓壮.基于不含负长度环有向图的Dijkstra算法[J].重庆邮电学院学报(自然科学版),2006(Z1). |
| |
| 作者姓名： | 尹方 邓壮 |
| |
| 作者单位： | 重庆邮电大学应用技术学院，重庆邮电大学应用技术学院 重庆 400065，重庆 400065 |
| |
| 摘 要： | Dijkstra算法是目前公认的较好的最短路径算法,单源点最短路径问题是最短路径问题家族中的核心问题之一。介绍了基于单源点最短路径问题在假定正权有向图上工作的Dijkstra算法以及算法的时间复杂度,同时又介绍了作了功能改进后的Dijkstra算法以及时间复杂度分析,并给出了算法实际工作于不含负长度环有向图的过程和结果。作了功能上的改进后,其算法能正常工作于不含负长度环的带权有向图中。
|
| 关 键 词： | Dijkstra算法 单源点最短路径 正权有向图 负长度环 |
Dijkstra algorithm base on directed graph without cycle of minus length |
| |
| YIN Fang,DENG Zhuang.Dijkstra algorithm base on directed graph without cycle of minus length[J].Journal of Chongqing University of Posts and Telecommunications(Natural Sciences Edition),2006(Z1). |
| |
| Authors: | YIN Fang DENG Zhuang |
| |
| Abstract: | In all shortest path algorithms, Dijkstra algorithm is fairly good acceptedly, Single-Source Shortest-Paths Problem is the core one in shortest path problem family. Base on Single-Source Shortest-Paths Problem, about function we improve Dijkstra algorithm work at positive weight direction graph. Then, Dijkstra algorithm can work at direction graph without cycle of minus length. |
| |
| Keywords: | Dijkstra algorithm single-source shortest-paths positive weight direction graph cycle of minus length |
| 本文献已被 CNKI 等数据库收录！ |
