图的最优矩阵构建研究  

Research on Optimal Matrix Construction of Diagram

作　　者：袁廷磊[1] 吾守尔.斯拉木 

机构地区：[1]新疆大学信息科学与工程学院,新疆乌鲁木齐830046

出　　处：《计算机技术与发展》2013年第7期151-154,175,共5页Computer Technology and Development

基　　金：新疆自治区科技计划项目(200732143)

摘　　要：为了提高图的最优矩阵的构建效率,文中通过对Floyd算法的研究,进一步提出了对其进行四层优化的方法,通过对图的矩阵中的特殊元素的删除和在计算前的判断减少了不必要的计算,加入贪心算法使其减少中间结果的生成,使中间结果更加接近图的最优矩阵。优化后的Floyd算法在很大程度上提高了执行效率,使其在实际应用中更加可取,经过逐步的优化使改进后的算法在运行时间上平均时间最多减少为原来的四分之一,而且随着图顶点数目的增加,修改后的Floyd算法效率有显著的提高,因此,在实际应用中是一个切实可行的算法。In order to improve the efficiency on construction of best matrix,through the Floyd algorithm, further propose its four optimization method,unnecessary calculation is reduced by the deletion of a particular element in FIG matrix and judgment before calculating,by adding a greedy algorithm to it reduce the generation of the intermediate result, the intermediate results are for closer to the best matrix. The optimized Floyd algorithm improves the efficiency of the implementation to a great extent, it is more desirable in practical applica- tions,the improved algorithm through a step-by-step optimization in the average time on the running time reduced to a maximum of a quarter of the original,but also with the increase in the number of vertices by the figure,the modified Floyd algorithm efficiency is signifi- cantly improved. Therefore,it is a practical algorithm in the practical application.

关 键 词：最短路径 FLOYD算法 贪心算法 最优矩阵 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]