| DAG中最短路径简单算法 |
| |
| 引用本文： | 周玉涛.DAG中最短路径简单算法[J].潍坊学院学报,2006,6(6):19-21. |
| |
| 作者姓名： | 周玉涛 |
| |
| 作者单位： | 潍坊学院,山东,潍坊,261061 |
| |
| 摘 要： | 针对DAG的特点,以拓扑排序为基础,提出了解决DAG的最短路径问题的简单算法。通过理论分析,表明该算法具有理想的运算效率,其中,解决单源点问题的运算时间与E成正比,解决所有点对问题的运算时间与VE成正比。拓扑排序策略对于此类最短路径问题的研究,较传统的方法运算简单、求解直观。
|
| 关 键 词： | 加权DAG 拓扑排序 边松弛 路径松弛 |
| 文章编号： | 1671-4288（2006）06-0019-03 |
| 收稿时间： | 2006-09-11 |
| 修稿时间： | 2006年9月11日 |
The Simple Algorithm of Finding Shortest Path of Weighted DAG |
| |
| ZHoU Yu-tao.The Simple Algorithm of Finding Shortest Path of Weighted DAG[J].Journal of Weifang University,2006,6(6):19-21. |
| |
| Authors: | ZHoU Yu-tao |
| |
| Institution: | Wei fang University ,Wei fang 261061 ,China |
| |
| Abstract: | Based on the characteristics of weighted DAG,the paper proposed an algorithm to solve the shortest path problems in the weighted DAG using topological sorting.The result shows that compared with traditional method,the proposed method has an excellent efficiency and low computational complexity and simple result representation.It is worthy not only at teaching but also at practice. |
| |
| Keywords: | weighted DAG topological sorting edge relaxation path relaxation |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
