資源描述：
《基于MapReduce的單源最短路徑算法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、基于MapReduce的單源最短路徑算法研究ResearchontheSingleSourceShortestPathAlgorithmUsingMapReduce(湖南大學(xué))楊玲李仁發(fā)唐卓YANGLingLIRen-faTANGZhuo摘要：通過對(duì)MapReduce模型執(zhí)行過程的分析，針對(duì)單源最短路徑算法難以隨著云計(jì)算的產(chǎn)生和發(fā)展而應(yīng)用及捉高搜索效率的問題，本文設(shè)計(jì)和實(shí)現(xiàn)了一種基于MapReduce架構(gòu)的并行單源最短路徑算法。并基于Hadoop平臺(tái)集群環(huán)境進(jìn)行了研究與實(shí)驗(yàn)，結(jié)果表明，文中算法可以有效地找出整個(gè)閤結(jié)構(gòu)中的單源最短路徑，且驗(yàn)證了算法性能的優(yōu)越性。關(guān)鍵詞：MapReduc
2、e;并行；最短路徑；hadoop中圖分類號(hào)：TP393.0文獻(xiàn)標(biāo)識(shí)碼：AAbstract:Viatheanalysistoimplementationprocessofmapreduce,aimmingattheproblemthatsinglesourceshortestpathalgorithmishardtobeusedwiththeappearanceanddevelopmentofcloudcomputingandtheproblemofsearchingefficiency,aparallelsinglesourceshortestpathalgorithmbasedon
3、mapreduceframeworkisdesignedandimplemented.researchandexperimentaredonebaseconhadoopplatform.Asshownbytheexperimentalresults,theproposedalgorithmcansearchthesinglesourceshortestpathefficientlyinthewholegraphicstructure,anditsgoodperformanceistestified.Keywords:MapReduce;Parallel;Shortestpath;Ha
4、doop1算法及其數(shù)據(jù)結(jié)構(gòu)的定義1.1單源最短路徑算法單源最短路徑是指給定一個(gè)帶權(quán)冇向圖G=(V,E,W),其中為頂點(diǎn)集,E為有向邊集,W為權(quán)集且每條邊的權(quán)是一個(gè)非負(fù)尖數(shù)。另外,還給定V中的一個(gè)頂點(diǎn)，稱為源，計(jì)算從源到所有3￡祀各頂點(diǎn)的最短路徑長度。這里的長度是指各邊權(quán)之和，根據(jù)不叵的實(shí)際情況，邊上權(quán)值的長度可以表示成吋間、距離、成木、損失.損耗或其它任何沿一條路徑的相加累積量,且為最小值。楊玲：碩士研究生圖3基于MapReduce的單源最短路徑算法的執(zhí)行過程(0&墀藥布翎媲鬲cmicJournalElectronicPublishingHouse.AI^e^vec◎if腆駅觀閱帯
5、阻946居曬借-97-引言計(jì)算機(jī)網(wǎng)絡(luò)的飛速發(fā)展促進(jìn)了云計(jì)算的產(chǎn)生。MapReduce并行編程模型是云計(jì)算的核心技術(shù)Z-.2005年4月6日Google實(shí)驗(yàn)室的JeffreyDean和SanjayGhemawat提出了MapReduce模型并進(jìn)行了詳細(xì)地闡述，它為并行系統(tǒng)的數(shù)據(jù)處理提供了一個(gè)簡(jiǎn)單、優(yōu)雅的解決方案。Apache基金會(huì)基于Jav;開發(fā)了一個(gè)分布式基礎(chǔ)架構(gòu)Hadoop,實(shí)現(xiàn)了MapReduce模型并提供了分布式計(jì)算平臺(tái)。在通信網(wǎng)絡(luò)與交通網(wǎng)絡(luò)中，并行問題和最短路徑問題-?首是研究的熱點(diǎn)，有看極其重要的作用。在處理實(shí)際問題的過秸中，通常將現(xiàn)實(shí)問題轉(zhuǎn)化為圖的網(wǎng)狀形式來研究最短路徑。
6、朮MapReduce并行計(jì)算模型的出現(xiàn)，為解決人規(guī)模數(shù)據(jù)處理問趣提供了一種新的途徑，也為最短路徑的并行計(jì)算帶來了一種新的解決方法，有效提高了計(jì)算效率。本文提出了基于MapReduce的單源最短路徑算法。首先利用MapReduce架構(gòu)來形成算法的并行化思想，分析并設(shè)計(jì)了算法的過程，然后通過Hadoop平臺(tái)來實(shí)現(xiàn)算法，最后對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了分析。1.2相關(guān)數(shù)據(jù)結(jié)構(gòu)定義為了減少數(shù)據(jù)冗余，本文對(duì)于圖的表示方法采用鄰接表的方式進(jìn)行存儲(chǔ)，以各頂點(diǎn)為中心,每一行代表圖中的一個(gè)頂點(diǎn)，各頂點(diǎn)數(shù)據(jù)結(jié)構(gòu)描述如下：山、djaxntmformoon]其中JD為頂點(diǎn)標(biāo)識(shí)distance表示從源點(diǎn)到頂點(diǎn)的距離?除
7、到本身的距離為0外，其余初始值皆為無窮大MAX:Flag為標(biāo)志位，其值可分別取0、120表示未處理的頂點(diǎn),1表示正待處理的頂點(diǎn),2表示已經(jīng)處理了的頂點(diǎn)，源點(diǎn)的初始值為1,其余頂點(diǎn)皆為O;Adjacentinfonnation代表鄰接信息，包括頂點(diǎn)的鄰接點(diǎn)及其權(quán)值。如圖1用鄰接表表示的數(shù)據(jù)結(jié)構(gòu)如圖2所示：■—T-?■—?JLX_AX>rrs=J?.—ri/-?"r2基于MapReduce的單源最短路徑算法的設(shè)計(jì)與實(shí)現(xiàn)MapReduce用戶用兩個(gè)函數(shù)表達(dá)這個(gè)計(jì)
