地理与地理信息科学
地理與地理信息科學
지리여지리신식과학
GEOGRAPHY AND TERRITORIAL RESEARCH
2013年
4期
17-20
,共4页
孙文彬%谭正龙%王江%周长江%何俊芳
孫文彬%譚正龍%王江%週長江%何俊芳
손문빈%담정룡%왕강%주장강%하준방
并行算法%最短路径算法%并行Boost库%网络分割%对向搜索
併行算法%最短路徑算法%併行Boost庫%網絡分割%對嚮搜索
병행산법%최단로경산법%병행Boost고%망락분할%대향수색
parallelization algorithm%shortest path algorithm%parallelization Boost library%network partition%Bidirectional search
常见的最短路径算法多是研究单源多汇或多源多汇问题,针对单源单汇最短路径并行算法的研究较少.为此,该文探讨基于并行Boost库、网络分割、对向搜索的最短路径并行算法;并应用DIMAS提供的路网数据进行了相关实验.结果表明:对向搜索的并行算法效率较高,算法耗时为串行Dijkstra算法的1/4～1/2.
常見的最短路徑算法多是研究單源多彙或多源多彙問題,針對單源單彙最短路徑併行算法的研究較少.為此,該文探討基于併行Boost庫、網絡分割、對嚮搜索的最短路徑併行算法;併應用DIMAS提供的路網數據進行瞭相關實驗.結果錶明:對嚮搜索的併行算法效率較高,算法耗時為串行Dijkstra算法的1/4～1/2.
상견적최단로경산법다시연구단원다회혹다원다회문제,침대단원단회최단로경병행산법적연구교소.위차,해문탐토기우병행Boost고、망락분할、대향수색적최단로경병행산법;병응용DIMAS제공적로망수거진행료상관실험.결과표명:대향수색적병행산법효솔교고,산법모시위천행Dijkstra산법적1/4～1/2.
