| 无回路网络中最短路问题的高效算法 |
| |
| 引用本文： | 冷洪泽,谢政,陈挚,徐桢.无回路网络中最短路问题的高效算法[J].计算机工程,2009,35(14):84-86. |
| |
| 作者姓名： | 冷洪泽 谢政 陈挚 徐桢 |
| |
| 作者单位： | 1. 国防科技大学理学院,长沙,410073
2. 北京航空航天大学电子信息工程学院,北京,100083 |
| |
| 基金项目： | 国家重点基础研究发展规划(973计划) |
| |
| 摘 要： | 无回路网络是一类重要的网络，给出在无回路网络中求解最短路树形图和任意顶点对间最短路的高效算法。该算法将顶点进行重新编号，结合广度优先探索法，从源顶点出发依次搜索每个顶点的所有出弧，并在弧的头部进行权值变换操作，可以得到最短路树形图和任意顶点对间最短路，算法复杂度分别为O(m)和O(m(n-m1/2))。该算法思想简便、复杂度低、易于操作。 关键词：
|
| 关 键 词： | 根 无回路网络 最短路树形图 |
| 修稿时间： | |
High-efficient Algorithm for Shortest Path Problem in DAG |
| |
| LENG Hong-ze,XIE Zheng,CHEN Zhi,XU Zhen.High-efficient Algorithm for Shortest Path Problem in DAG[J].Computer Engineering,2009,35(14):84-86. |
| |
| Authors: | LENG Hong-ze XIE Zheng CHEN Zhi XU Zhen |
| |
| Affiliation: | 1.College of Science;National University of Defense Technology;Changsha 410073;2.School of Electronics and Information Engineering;Beijing University of Aeronautics and Astronautics;Beijing 100083 |
| |
| Abstract: | Directed Acyclic Graph(DAG) is a kind of important network.A high-efficient algorithm to seek the shortest path arborescence and all shortest paths between any two vertices in DAG is presented.Arranging the vertices over again and using breadth first search for reference,this algorithm checks all out-arcs of each vertex starting with the source,and transforms the length values of the shortest paths at the head of each arc,and then it can get the shortest path arborescence and all shortest paths between any ... |
| |
| Keywords: | root Directed Acyclic Graph(DAG) shortest path arborescence |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
