复杂网络中近似最短路径问题

• 作者: 刘微 肖华勇
• 来源期刊: 计算机系统应用
• 关键词: 复杂网络 树分解 树宽 树 最短路径近似算法
• 年，卷（期）: 2016,（5）
• 页码范围: 107-112
• 页数: 6页
• 字数: 5339字
• 语种: 中文

摘要

随着网络规模的不断增大，经典算法(如Dijkstra等)效率越来越低。针对这一问题，研究者们提出了许多近似搜索算法，但如何既能提高搜索效率又能保持准确性一直是一大难点。本文根据复杂网络的结构特性引入区域划分，同时改进树分解的构造，将图构造成一棵树进行搜索，得到了一个新的适合于复杂网络的最短路径近似算法。此外通过实例验证，该算法不仅在一定程度上降低了计算复杂性，而且保持了较高的近似准确性。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	肖华勇	西北工业大学理学院	31	146	7.0	10.0
2	刘微	西北工业大学理学院	2	5	2.0	2.0