{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T02:42:55Z","timestamp":1747190575332,"version":"3.40.5"},"reference-count":41,"publisher":"Wiley","license":[{"start":{"date-parts":[[2021,5,31]],"date-time":"2021-05-31T00:00:00Z","timestamp":1622419200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Key R&D Plan of China","award":["2018YFC1406203","SDYY17040","2019KJN024"],"award-info":[{"award-number":["2018YFC1406203","SDYY17040","2019KJN024"]}]},{"name":"Shandong Postgraduate Tutor Guidance Ability Improvement Project","award":["2018YFC1406203","SDYY17040","2019KJN024"],"award-info":[{"award-number":["2018YFC1406203","SDYY17040","2019KJN024"]}]},{"DOI":"10.13039\/501100018627","name":"Science and Technology Support Plan of Youth Innovation Team of Shandong Higher School","doi-asserted-by":"crossref","award":["2018YFC1406203","SDYY17040","2019KJN024"],"award-info":[{"award-number":["2018YFC1406203","SDYY17040","2019KJN024"]}],"id":[{"id":"10.13039\/501100018627","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Scientific Programming"],"published-print":{"date-parts":[[2021,5,31]]},"abstract":"<jats:p>The multistage graph problem is a special kind of single-source single-sink shortest path problem. It is difficult even impossible to solve the large-scale multistage graphs using a single machine with sequential algorithms. There are many distributed graph computing systems that can solve this problem, but they are often designed for general large-scale graphs, which do not consider the special characteristics of multistage graphs. This paper proposes DMGA (Distributed Multistage Graph Algorithm) to solve the shortest path problem according to the structural characteristics of multistage graphs. The algorithm first allocates the graph to a set of computing nodes to store the vertices of the same stage to the same computing node. Next, DMGA calculates the shortest paths between any pair of starting and ending vertices within a partition by the classical dynamic programming algorithm. Finally, the global shortest path is calculated by subresults exchanging between computing nodes in an iterative method. Our experiments show that the proposed algorithm can effectively reduce the time to solve the shortest path of multistage graphs.<\/jats:p>","DOI":"10.1155\/2021\/6639008","type":"journal-article","created":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T20:27:08Z","timestamp":1622579228000},"page":"1-14","source":"Crossref","is-referenced-by-count":0,"title":["DMGA: A Distributed Shortest Path Algorithm for Multistage Graph"],"prefix":"10.1155","volume":"2021","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9251-680X","authenticated-orcid":true,"given":"Huanqing","family":"Cui","sequence":"first","affiliation":[{"name":"College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao, Shandong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6915-7717","authenticated-orcid":true,"given":"Ruixue","family":"Liu","sequence":"additional","affiliation":[{"name":"College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao, Shandong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0422-1180","authenticated-orcid":true,"given":"Shaohua","family":"Xu","sequence":"additional","affiliation":[{"name":"College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao, Shandong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8325-6049","authenticated-orcid":true,"given":"Chuanai","family":"Zhou","sequence":"additional","affiliation":[{"name":"College of Business, Qingdao Binhai University, Qingdao, Shandong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","reference":[{"key":"1","doi-asserted-by":"publisher","DOI":"10.1109\/WCSE.2009.819"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1109\/CCDC.2016.7532149"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.3390\/a10040115"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2019.102582"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1016\/j.seta.2019.100582"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTER.2016.50"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"first-page":"17","article-title":"PowerGraph: distributed graph-parallel computation on natural graphs","author":"J. E. Gonzalez","key":"8"},{"first-page":"599","article-title":"GraphX: graph processing in a distributed dataflow framework","author":"J. E. Gonzalez","key":"9"},{"key":"10","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484427"},{"issue":"8","key":"11","doi-asserted-by":"crossref","first-page":"716","DOI":"10.14778\/2212351.2212354","article-title":"Distributed GraphLab: a framework for machine learning and data mining in the cloud","volume":"5","author":"Y. Low","year":"2012","journal-title":"Proceeding of the VLDB Endowment"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741970"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904486"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2017.06.027"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806424"},{"key":"16","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"2009","edition":"3rd"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.45"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1145\/2925426.2926287"},{"key":"19","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2485994"},{"key":"20","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.24"},{"key":"21","doi-asserted-by":"publisher","DOI":"10.1109\/CIS2018.2018.00016"},{"key":"22","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188948"},{"key":"23","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2908011"},{"key":"24","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2018.00072"},{"key":"25","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236208"},{"key":"26","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-019-07256-z"},{"key":"27","doi-asserted-by":"publisher","DOI":"10.1109\/IA349570.2019.00013"},{"key":"28","doi-asserted-by":"publisher","DOI":"10.1109\/SASO.2013.13"},{"issue":"11","key":"29","doi-asserted-by":"crossref","first-page":"2710","DOI":"10.1109\/TPDS.2020.3001645","article-title":"High-quality shared-memory graph partitioning","volume":"31","author":"Y. Akhremtsev","year":"2020","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"30","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556213"},{"key":"31","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2018.00033"},{"key":"32","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2019.06.033"},{"key":"33","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2019.00031"},{"key":"34","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2020.3002150"},{"key":"35","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2955494"},{"key":"36","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989438"},{"key":"37","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2789993"},{"key":"38","doi-asserted-by":"publisher","DOI":"10.1145\/3287324.3287551"},{"first-page":"689","article-title":"A parallel priority data structure with applications","author":"G. S. Brodal","key":"39"},{"key":"40","doi-asserted-by":"publisher","DOI":"10.1145\/1187436.1216585"},{"first-page":"1811","article-title":"Dijkstra\u2019s shortest path algorithm serial and parallel execution performance analysis","author":"N. Jasika","key":"41"}],"container-title":["Scientific Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/sp\/2021\/6639008.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/sp\/2021\/6639008.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/sp\/2021\/6639008.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T20:27:17Z","timestamp":1622579237000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.hindawi.com\/journals\/sp\/2021\/6639008\/"}},"subtitle":[],"editor":[{"given":"Cristian","family":"Mateos","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2021,5,31]]},"references-count":41,"alternative-id":["6639008","6639008"],"URL":"https:\/\/doi.org\/10.1155\/2021\/6639008","relation":{},"ISSN":["1875-919X","1058-9244"],"issn-type":[{"type":"electronic","value":"1875-919X"},{"type":"print","value":"1058-9244"}],"subject":[],"published":{"date-parts":[[2021,5,31]]}}}