| ���ڡ�������������̾�·�㷨 |
| |
| 引用本文： | 张云丽,莫辉辉,邓连波.���ڡ�������������̾�·�㷨[J].交通运输系统工程与信息,2004,4(2):56-58. |
| |
| 作者姓名： | 张云丽 莫辉辉 邓连波 |
| |
| 作者单位： | ????????????乤????????????410075 |
| |
| 摘 要： | 最短径路是网络优化中的一个经典问题，Dijkstra算法被公认为是一种十分有效的最短径路的搜索求解算法．本在研究网络一般结构特点的基础上，发现传统Dijkstra算法在每次迭代过程中都需要搜索所有节点的这一缺陷，通过向搜索节点中引入“度”的信息，提出了基于“度搜索”的改进算法，并根据网络的特点，给出了有向网络和无向网络两种情况下存在“度”差异的算法设计方法；算法的整体结构与Dijkstra保持了一致性，没有算法结构的突变，因而通过修改原有Dijkstra程序和重新设计“度搜索”程序都十分容易实现．该算法提高了最短径路的搜索效率，特别是对稀疏网络，算法效率更为明显，其复杂度小于O(｜V｜^2)．
|
| 关 键 词： | ???????? ????· Dijkstra?? ?????? |
| 文章编号： | 1009-6744(2004)02-0056-03 |
| 修稿时间： | 2003年9月22日 |
An Improved Shortest Path Algorithm Based on Vertex Degree Search |
| |
| ZHANG Yun-li,MO Hui-hui,DENG Lian-bo.An Improved Shortest Path Algorithm Based on Vertex Degree Search[J].Transportation Systems Engineering and Information,2004,4(2):56-58. |
| |
| Authors: | ZHANG Yun-li MO Hui-hui DENG Lian-bo |
| |
| Institution: | School of Traffic and Transportation Engineering, Central South University, Changsha??410075??China |
| |
| Abstract: | |
| |
| Keywords: | shortest path dijkstra algorithm vertex degree search |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《交通运输系统工程与信息》浏览原始摘要信息 |
| 点击此处可从《交通运输系统工程与信息》下载免费的PDF全文 |
