论文部分内容阅读
本文对最短路径算法的优化及实现过程进行了研究。文章提出了一种方便的解决方案，在内存中开辟数组，将数组的下标与某结点点号相对应，可以快速计算出该结点的出度，从而通过弧段起点数组和弧段终点数组的对应关系可以找到该结点的邻接点。最后，在对Dijkstra算法的实现过程中，对其中的一个关键步骤——搜索最小权值的顶点进行了优化，针对快速排序算法的不稳定性，提出了改进的搜索方案，使用折半插入排序函数对最短路径值数组重新进行地址排序，以减少查找次数，提高排序的效率。可使排序的平均时间复杂度从O(n<2>)降低到O(n)。通过对优化算法的评价，表明了本文提出的优化算法是高效率的。