分布式环境下基于路径阻断的APSP算法研究

发布时间：2025-04-27 00:55

　　随着大数据时代的到来,数据成爆炸式增长,随之出现的网络规模越来越大,网络结构也越来越复杂。在大规模复杂关系网络中蕴含着巨大的研究价值,其中求解全源最短路径(All Pairs Shortest Paths,APSP)是研究大规模复杂网络的一个基本问题。传统的求解APSP的算法在大规模复杂网络下效率不高,而引入路径阻断的算法相对于传统的算法在复杂网络下表现出较好的性能。由于大规模复杂网络中,数据量较大,在单机下计算速度较慢,因此,本文提出分布式环境下引入路径阻断的BFS算法来解决大规模复杂网络下求解APSP的问题。首先本课题在志愿计算框架下对引入路径阻断的算法进行阐述,并通过实验证明,在大规模复杂网络下,引入路径阻断的算法比传统的算法效率要高。其次,通过对引入路径阻断的算法进行分析,我们提出三种优化策略,即基于层数,基于入队个数,以及基于层数和入队个数。这三种优化策略通过严格阻断点条件,阻止不适合的阻断点进入阻断过程,从而提高算法效率。最后,本课题通过实验对上述算法进行实验验证。本文通过多个公开数据集对上述方法进行实验验证,这些数据集都是公开且真实的。实验结果表明在大规模复杂网络下,用志愿...

【文章页数】：71 页

【学位级别】：硕士

【部分图文】：

图３－１网络节点图??Ｆｉ．３－１?Ｔｈｅ?ｎｏｄｅ?ｏｆ?ｎｅｔｗｏｒｋ??

图３－１网络节点图??Ｆｉｇ．３－１?Ｔｈｅ?ｎｏｄｅ?ｏｆ?ｎｅｔｗｏｒｋ??图３－１表示我们将要进行计算的图，其中图的节点用英文字母标识的圆圈来代表，??这些节点通过以实线表示的边进行连接，通过这些，构成了一个简单的无权无向图。??在这些节点中，节点ｖ表示我们需要求解单源最短....

图３－２阻断点为ｕ的图??－

?〇??图３－１网络节点图??Ｆｉｇ．３－１?Ｔｈｅ?ｎｏｄｅ?ｏｆ?ｎｅｔｗｏｒｋ??图３－１表示我们将要进行计算的图，其中图的节点用英文字母标识的圆圈来代表，??这些节点通过以实线表示的边进行连接，通过这些，构成了一个简单的无权无向图。??在这些节点中，节点ｖ表示我们需要求解....

图３－３阻断点为ｄ的图??Ｆｉｇ．３－３?Ｂｌｏｃｋｉｎｇ?Ｇｒａｐｈ?ｗｉｔｈ?ｔｈｅ?ｎｏｄｅ?ｄ??

最短路径为ｄｉｖ［ｄ］［ｖ］＋ｄｉｖ［ｄ］［ｂ］，而根据图我们司以明显看出，从节点ｖ到节点ｂ的最??短路径是ｖ－ｕ－ａ－ｂ。因此，用节点ｄ作为阻断点计算节点ｖ的单源最短路径时，得到的??结果是不准确的。如图３－３所示，其中灰色标注的节点ｄ为阻断点。??〇??图３－３阻断点为ｄ的图....

图4-4Levelblock和enqueue_卜lock比较

通过图４－３，我们可知，利用入队个数进行优化的算法在分布式系统下优于引入??路径阻断的算法。同时，对图４－４进行观察分析，可知，根据层数和根据入队个数两??３９??

本文编号：4041631