【摘要】 用Ｄｉｊｋｓｔｒａ算法，可求出单源单汇点最短路径，时间复杂性是Ｏ（ｎ２）．笔者提出了一种求最短路径的算法，时间复杂性是Ｏ（ｎ＋ｅ）（其中ｎ是图中顶点数，ｅ是边数），且两种算法的空间复杂性基本相同。更多还原

【Abstract】 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.更多还原