基于Dijkstra算法的一种最短路径优化算法

摘要

详细介绍了经典的Dijkstra算法,举例说明了该算法的实现方法以及该算法的缺点:即需要网络结点数平方级的内存;同时详细说明了一种基于Dijkstra算法的优化算法--邻接结点算法,该算法充分利用了网络拓扑信息中的弧段的连接关系,避免了使用含有大量无穷值的关联矩阵,使之更适合带有拐向限制设置的最短路径算法和大量结点的实际数据.实践证明,该算法可以节约大量的内存,对于结点数比较大的网络,或带有大量拐向限制设置的网络,具有较好的适用性.