基于MapReduce的单源最短路径算法研究

《基于MapReduce的单源最短路径算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于MapReduce的单源最短路径算法研究ResearchontheSingleSourceShortestPathAlgorithmUsingMapReduce(湖南大学)杨玲李仁发唐卓YANGLingLIRen-faTANGZhuo摘要：通过对MapReduce模型执行过程的分析，针对单源最短路径算法难以随着云计算的产生和发展而应用及捉高搜索效率的问题，本文设计和实现了一种基于MapReduce架构的并行单源最短路径算法。并基于Hadoop平台集群环境进行了研究与实验，结果表明，文中算法可以有效地找出整个閤结构中的单源最短路径，且验证了算法性能的优越性。关键词：MapReduc

2、e;并行；最短路径；hadoop中图分类号：TP393.0文献标识码：AAbstract:Viatheanalysistoimplementationprocessofmapreduce,aimmingattheproblemthatsinglesourceshortestpathalgorithmishardtobeusedwiththeappearanceanddevelopmentofcloudcomputingandtheproblemofsearchingefficiency,aparallelsinglesourceshortestpathalgorithmbasedon

3、mapreduceframeworkisdesignedandimplemented.researchandexperimentaredonebaseconhadoopplatform.Asshownbytheexperimentalresults,theproposedalgorithmcansearchthesinglesourceshortestpathefficientlyinthewholegraphicstructure,anditsgoodperformanceistestified.Keywords:MapReduce;Parallel;Shortestpath;Ha

4、doop1算法及其数据结构的定义1.1单源最短路径算法单源最短路径是指给定一个带权冇向图G=(V,E,W),其中为顶点集,E为有向边集,W为权集且每条边的权是一个非负尖数。另外,还给定V中的一个顶点，称为源，计算从源到所有3£祀各顶点的最短路径长度。这里的长度是指各边权之和，根据不叵的实际情况，边上权值的长度可以表示成吋间、距离、成木、损失.损耗或其它任何沿一条路径的相加累积量,且为最小值。杨玲：硕士研究生图3基于MapReduce的单源最短路径算法的执行过程(0&墀药布翎媲鬲cmicJournalElectronicPublishingHouse.AI^e^vec◎if腆駅觀阅帯

5、阻946居晒借-97-引言计算机网络的飞速发展促进了云计算的产生。MapReduce并行编程模型是云计算的核心技术Z-.2005年4月6日Google实验室的JeffreyDean和SanjayGhemawat提出了MapReduce模型并进行了详细地阐述，它为并行系统的数据处理提供了一个简单、优雅的解决方案。Apache基金会基于Jav;开发了一个分布式基础架构Hadoop,实现了MapReduce模型并提供了分布式计算平台。在通信网络与交通网络中，并行问题和最短路径问题-•首是研究的热点，有看极其重要的作用。在处理实际问题的过秸中，通常将现实问题转化为图的网状形式來研究最短路径。

6、朮MapReduce并行计算模型的出现，为解决人规模数据处理问趣提供了一种新的途径，也为最短路径的并行计算带来了一种新的解决方法，有效提高了计算效率。本文提出了基于MapReduce的单源最短路径算法。首先利用MapReduce架构來形成算法的并行化思想，分析并设计了算法的过程，然后通过Hadoop平台來实现算法，最后对实验结果进行了分析。1.2相关数据结构定义为了减少数据冗余，本文对于图的表示方法采用邻接表的方式进行存储，以各顶点为中心,每一行代表图中的一个顶点，各顶点数据结构描述如下：山、djaxntmformoon]其中JD为顶点标识distance表示从源点到顶点的距离•除

7、到本身的距离为0外，其余初始值皆为无穷大MAX:Flag为标志位，其值可分别取0、120表示未处理的顶点,1表示正待处理的顶点,2表示已经处理了的顶点，源点的初始值为1,其余顶点皆为O;Adjacentinfonnation代表邻接信息，包括顶点的邻接点及其权值。如图1用邻接表表示的数据结构如图2所示：■—T-•■—•JLX_AX>rrs=J«.—ri/-»"r2基于MapReduce的单源最短路径算法的设计与实现MapReduce用户用两个函数表达这个计