单源点最短路径动态优化算法

The Dynamic Optimum Algorithm of the Shortest Path of Single Source Vertex

设计了最短路径时间复杂度取决于边数e和点数n的动态优化算法。采用了独特的动态PV集合链,改进了当前求得的最短路径向量D的存储结构,用PV集合链对向量D进行动态管理,使其时间开销为e+(n-1)×(n-2)/2+3n。当n>4时,SPD OA算法的性能明显优于Dijkstra算法,呈现出良好的动态优化特性。最后对动态优化算法与Dijkstra算法用理论公式得出的数据进行了时间性能比较。

This paper designs the Shortest Path Dynamic Optimum Algorithm（SPDOA） whose time complexity is decided by.the union of the number of edge and the number of vertex,adopts a unique link of PV aggregate,mends the storage structure of currently computing the Shortest Path D vector,makes use of link of PV aggregate to dynamically manage D vector,to attain a spending of time which equals to e＋（n-1）×（n-2）/2＋3n.While n〉4,the performance of SPDOA is distinctly better than the ones of Dijkstra,the dynamic characteristic is excel.At last,this paper draws comparisons between SPDOA and Dijkstra with the formulas of theory.