摘要
用Ｄｉｊｋｓｔｒａ算法，可求出单源单汇点最短路径，时间复杂性是Ｏ（ｎ２）．笔者提出了一种求最短路径的算法，时间复杂性是Ｏ（ｎ＋ｅ）（其中ｎ是图中顶点数，ｅ是边数），且两种算法的空间复杂性基本相同。
It is well known that the optimal paths between nodes will be solved by Dijkstra’s algorithm with the time complexity O(n).In this paper,3 new algorithm for this problem is presented,and it is proved that the time com-plexity of the algorithm is O(n+e),where n denotes the number of nodes and e denotes the number of degrees.
出处
《江苏理工大学学报（自然科学版）》
1995年第6期65-67,共3页
Journal of Jiangsu University of Science and Technology(Natural Science)
关键词
算法
最短路径
单源单汇点
无环图
algorithm
optimal path
time complexity
space complexity
