基于存储结构的Dijkstra算法优化

Optimized Dijkstra Algorithm Based on Storage Structure

在求解最短路径时经常使用经典的Dijkstra算法,但在实际应用中在计算最短路径长度时需要进行大量的数据比较,而当图中两顶点之间的距离是∞时,是没有必要进行比较的。本文从存储结构上讨论如何对Dijkstra算法进行优化,尽量减少数据比较次数。

In short path calculating, the classical Dijkstra algorithm is often used, but it requires the comparison among large amounts of data. Moreover ,those data comparison is not necessarily made when the distance between the two nodes in a graph equals infiniteness. Therefore, this paper attempts to analyse optimization for Dijkstra algorithm in terms of storage structure, hence reducing the frequency of data comparison as possible as it can.