最短路径算法效率研究

Research into the Efficiency of the Shortest Path Problem Algorithm

从经典的最短路径算法—Dijkstra算法入手,针对同一算法,分别采用三种不同的存储结构存储临时标号节点,通过对无序结构、桶结构、堆结构存储的分析与比较,提出基于堆结构的Dijkstra算法的效率高于其他两种算法,特别适合于大规模网络。

For the same algorithm, three different storage structures, out-of-order structure, bucket structure and heap structure, are adopted to save temporary label nodes. After comparison and analysis, the efficiency of Dijkstra algorithm, based on heap structure, is higher than the othertwo and is especially adaptable to large-scale networks.