Pathfinder算法优化研究-计算机应用与软件.PDF

第３２卷第１１期　　　 计算机应用与软件 Ｖｏｌ３２Ｎｏ．１１ ２０１５年１１月　　 ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅ Ｎｏｖ．２０１５ Ｐａｔｈｆｉｎｄｅｒ算法优化研究 汤 天 波 （上海市科学学研究所　上海２００２３５） 摘　要　　Ｐａｔｈｆｉｎｄｅｒ算法是复杂网络分析及可视化的重要方法，但现有算法时间复杂度大，难以在大数据环境下广泛应用。提出 一种基于Ｐｒｉｍ算法的Ｐａｔｈｆｉｎｄｅｒ优化算法，在求解复杂网络图的最小生成树的过程中，通过距离矩阵计算得到Ｐａｔｈｆｉｎｄｅｒ算法的结 ２ 果图。算法时间复杂度可稳定为Ｏ（ｎ）。实验结果表明，在顶点数为５００的稠密网络上，该算法的运行时间有较大的优势。 关键词　　复杂网络　可视化　Ｐａｔｈｆｉｎｄｅｒ算法　Ｐｒｉｍ算法 中图分类号　ＴＰ３　　　　文献标识码　Ａ　　　　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００３８６ｘ．２０１５．１１．０６４ ＲＥＳＥＡＲＣＨＯＮＰＡＴＨＦＩＮＤＥＲＡＬＧＯＲＩＴＨＭＯＰＴＩＭＩＳＡＴＩＯＮ ＴａｎｇＴｉａｎｂｏ （ＳｈａｎｇｈａｉＩｎｓｔｉｔｕｔｅｆｏｒＳｃｉｅｎｃｅｏｆＳｃｉｅｎｃｅ，Ｓｈａｎｇｈａｉ２００２３５，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ　　Ｐａｔｈｆｉｎｄｅｒａｌｇｏｒｉｔｈｍｉｓａｎｉｍｐｏｒｔａｎｔｍｅｔｈｏｄｆｏｒｃｏｍｐｌｅｘｎｅｔｗｏｒｋａｎａｌｙｓｉｓａｎｄｖｉｓｕａｌｉｓａｔｉｏｎ．Ｈｏｗｅｖｅｒ，ｔｈｅｔｉｍｅｃｏｍｐｌｅｘｉｔｙｏｆ ｅｘｉｓｔｉｎｇａｌｇｏｒｉｔｈｍｓｉｓｔｏｏｂｉｇｔｏｂｅｗｉｄｅｌｙａｐｐｌｉｅｄｉｎｂｉｇｄａｔａｅｎｖｉｒｏｎｍｅｎｔ．ＷｅｐｒｏｐｏｓｅｄａＰｒｉｍａｌｇｏｒｉｔｈｍｂａｓｅｄｏｐｔｉｍｉｓａｔｉｏｎｏｆＰａｔｈｆｉｎｄｅｒａｌ ｇｏｒｉｔｈｍ，ｗｈｉｃｈｃａｎｇｅｔｔｈｅｒｅｓｕｌｔｇｒａｐｈｏｆＰａｔｈｆｉｎｄｅｒａｌｇｏｒｉｔｈｍｂｙｃａｌｃｕｌａｔｉｎｇｔｈｅｄｉｓｔａｎｃｅｍａｔｒｉｘｉｎｔｈｅｐｒｏｃｅｓｓｏｆｓｏｌｖｉｎｇｔｈｅｍｉｎｉｍｕｍｓｐａｎ ２ ｎｉｎｇｔｒｅｅｏｆｔｈｅｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓｇｒａｐｈ．ＴｈｅｔｉｍｅｃｏｍｐｌｅｘｉｔｙｏｆｔｈｅａｌｇｏｒｉｔｈｍｃａｎｂｅｌｅｖｅｌｌｅｄｏｆｆｔｏＯ（ｎ）．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔ ｔｈｅａｌｇｏｒｉｔｈｍｈａｓａｇｒｅａｔａｄｖａｎｔａｇｅｉｎｒｕｎｎｉｎｇｔｉｍｅｏｎｄｅｎｓｅｎｅｔｗｏｒｋｓｗｉｔｈｖｅｒｔｅｘｎｕｍｂｅｒｏｆ５００． Ｋｅｙｗｏｒｄｓ　　Ｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ　Ｖｉｓｕａｌｉｓａｔｉｏｎ　Ｐａｔｈｆｉｎｄｅｒａｌｇｏｒｉｔｈｍ　Ｐｒｉｍａｌｇｏｒｉｔｈｍ ｋ １／ｒ ｗ（Ｐ）＝[ ｒ] （１） ｗ ０　引　言