{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T06:29:33Z","timestamp":1777703373049,"version":"3.51.4"},"reference-count":33,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2018,3,22]],"date-time":"2018-03-22T00:00:00Z","timestamp":1521676800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Intelligent &amp; Fuzzy Systems"],"published-print":{"date-parts":[[2018,3,22]]},"abstract":"<jats:p>Computing the all pair shortest paths in a graph is a widely used solution, but a time-consuming process too. The popularly used conventional algorithms rely solely on the computing capability of the CPU, but fail to meet the demand of real-time processing and mostly do not scale well for larger data. In this paper, we propose the ex-FTCD (extending Full Transitive Closure with Dijkstra\u2019s) algorithm for finding the all pair shortest path by merging the features of the greedy technique in Dijkstra\u2019s single source shortest path method and the transitive closure property. Experiments show that the process improves computing speed and is more scalable. We re-designed the algorithm for the parallel execution and implemented it in mapreduce on Hadoop that supports the conventional map\/reduce jobs. This work also includes the implementation on Spark that supports the in-memory computational capability which uses Random Access Memory for computations. The experiments show that the numbers of iterations are relatively small for even large networks.<\/jats:p>","DOI":"10.3233\/jifs-169458","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T12:25:44Z","timestamp":1521807944000},"page":"1643-1652","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":6,"title":["ex-FTCD: A novel mapreduce model for distributed multi source shortest path problem"],"prefix":"10.1177","volume":"34","author":[{"given":"R.G.","family":"Gayathri","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Amrita Vishwa Vidyapeetham, Amritapuri, Tamil Nadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jyothisha J.","family":"Nair","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Amrita Vishwa Vidyapeetham, Amritapuri, Tamil Nadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2018,3,22]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2427795"},{"issue":"69","key":"e_1_3_1_3_2","first-page":"222","article-title":"Towards efficient analysis of massive networks","volume":"10","author":"Gayathri R.G.","year":"2015","unstructured":"GayathriR.G. and NairJ.J., Towards efficient analysis of massive networks, International Journal of Applied Engineering Research10(69) (2015), 222\u2013227.","journal-title":"International Journal of Applied Engineering Research"},{"key":"e_1_3_1_4_2","volume-title":"Introduction to Algorithms","author":"Cormen T.","year":"2001","unstructured":"CormenT., LeisersonC., RivestR. and SteinC., Introduction to Algorithms, McGraw-Hill, 2001."},{"key":"e_1_3_1_5_2","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra E.W.","year":"1959","unstructured":"DijkstraE.W., A note on two problems in connexion with graphs, Numerische Mathematik1 (1959), 26\u2013271. doi:10.1007\/BF01386390","journal-title":"Numerische Mathematik"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/102435"},{"issue":"2","key":"e_1_3_1_7_2","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart P.E.","year":"1968","unstructured":"HartP.E., NilssonN.J. and RaphaelB., A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems Science and Cybernetics SSC44(2) (1968), 100\u2013107.","journal-title":"IEEE Transactions on Systems Science and Cybernetics SSC4"},{"issue":"6","key":"e_1_3_1_8_2","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","article-title":"Robert, Algorithm 97: Shortest path","volume":"5","author":"Floyd W.","year":"1962","unstructured":"FloydW., Robert, Algorithm 97: Shortest path, Communications of the ACM5(6) (1962), 345. doi:10.1145\/ 367766.368168","journal-title":"Communications of the ACM"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/996546.996553"},{"issue":"1","key":"e_1_3_1_11_2","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1145\/321992.321993","article-title":"Efficient algorithms for shortest paths in sparse networks","volume":"24","author":"Johnson D.B.","year":"1977","unstructured":"JohnsonD.B., Efficient algorithms for shortest paths in sparse networks, Journal of the ACM24(1) (1977), 113. doi:10.1145\/321992.321993","journal-title":"Journal of the ACM"},{"key":"e_1_3_1_12_2","unstructured":"David ForneyG.Jr The Viterbi Algorithm: A Personal History; 2005."},{"issue":"11","key":"e_1_3_1_13_2","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1145\/363269.363610","article-title":"Algorithm 360: Shortest-path forestwith topological ordering [h]","volume":"12","author":"Dial R.B.","year":"1969","unstructured":"DialR.B., Algorithm 360: Shortest-path forestwith topological ordering [h], Communications of the ACM12(11) (1969), 632\u2013633.","journal-title":"Communications of the ACM"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_1_15_2","article-title":"All-pairs Shortest Path Algorithm Based On MPI+CUDA Distributed Parallel Programming Model","author":"Wu Q.","year":"2013","unstructured":"WuQ., TongC., WangQ. and ChengX., All-pairs Shortest Path Algorithm Based On MPI+CUDA Distributed Parallel Programming Model, Journal of Networks (2013).","journal-title":"Journal of Networks"},{"key":"e_1_3_1_16_2","first-page":"218","volume-title":"Comparison of the efficiency of MapReduce and bulk synchronous parallel approaches to large network processing","author":"Kajdanowicz T.","year":"2012","unstructured":"KajdanowiczT., IndykW., KazienkoP. and KukulJ., Comparison of the efficiency of MapReduce and bulk synchronous parallel approaches to large network processing, in Proc of the 2012 IEEE 12th International Conference on Data Mining Workshops (ICDMW 12) (2012), 218\u2013225."},{"key":"e_1_3_1_17_2","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/j.engappai.2015.02.008","article-title":"A Map Reduce-based approach for shortest path problem in large-scale networks","volume":"41","author":"Aridhi S.","year":"2015","unstructured":"AridhiS., LacommeP., RenL. and VincentB., A Map Reduce-based approach for shortest path problem in large-scale networks, Engineering Applications of Articial Intelligence, Elsevier41 (2015), 151\u2013165. ISSN0952-1976.","journal-title":"Engineering Applications of Articial Intelligence, Elsevier"},{"key":"e_1_3_1_18_2","first-page":"355","volume-title":"Optimal distributed all pairs shortest paths and applications","author":"Holzer S.","year":"2012","unstructured":"HolzerS. and WattenhoferR., Optimal distributed all pairs shortest paths and applications, In Proceedings of the 2012 ACM symposium on Principles of distributed computing (PODC \u201912). ACM New York, NY, USA, (2012), 355\u2013364."},{"key":"e_1_3_1_19_2","doi-asserted-by":"crossref","first-page":"995","DOI":"10.1016\/j.procs.2016.07.297","article-title":"Extending full transitive closure to rank removable edges in GN algorithm","volume":"93","author":"Gayathri R.G.","unstructured":"GayathriR.G., NairJ.J. and KaimalM.R., Extending full transitive closure to rank removable edges in GN algorithm, Procedia Computer Science93 (1002), 995\u20131002 ISSN1877-0509.","journal-title":"Procedia Computer Science"},{"issue":"9","key":"e_1_3_1_20_2","doi-asserted-by":"crossref","first-page":"31","DOI":"10.5120\/13424-1104","article-title":"Article: Performance analysis of single source shortest path algorithm over multiple GPUs in a network of workstations using open CL and MPI","volume":"77","author":"Thouti K.","year":"2013","unstructured":"ThoutiK. and SatheS.R., Article: Performance analysis of single source shortest path algorithm over multiple GPUs in a network of workstations using open CL and MPI, International of Journal of Computer Applications77(9) (2013), 31\u201336.","journal-title":"International of Journal of Computer Applications"},{"key":"e_1_3_1_21_2","unstructured":"KanchiS. and VineyardD. An optimal distributed algorithm for All pairs shortest path."},{"key":"e_1_3_1_22_2","unstructured":"RavichandranA. MenonS.G. and ShyamasundarR.K. A distributed algorithm for finding the shortest paths in an undirected graph Technical Report CS-86-13 Department of Compute Science Pennsylvania State University; 1986."},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/358690.358717"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28421"},{"key":"e_1_3_1_25_2","unstructured":"TouegS. An all-pairs shortest-path distributed algorithm Res Rep RC-8327IBM Thomas J. Watson Research Center Yorktown Heights N.Y.; (1980)."},{"key":"e_1_3_1_26_2","first-page":"599","volume-title":"Graph X: Graph processing in a distributed data flow frameworkProceedings of the 11th USENIX conference on Operating Systems Design and Implementation (OSDI\u201914)","author":"Gonzalez J.E.","year":"2014","unstructured":"GonzalezJ.E., XinR.S., DaveA., CrankshawD., FranklinM.J. and StoicaI., Graph X: Graph processing in a distributed data flow framework, In Proceedings of the 11th USENIX conference on Operating Systems Design and Implementation (OSDI\u201914). USENIX Association, Berkeley, CA, USA, (2014), 599\u2013613."},{"issue":"2","key":"e_1_3_1_27_2","doi-asserted-by":"crossref","first-page":"751","DOI":"10.1109\/TNET.2016.2604278","article-title":"Are we connected? Optimal determination of source destination connectivity in random networks","volume":"25","author":"Fu L.","year":"2017","unstructured":"FuL., WangX. and KumarP.R., Are we connected? Optimal determination of source destination connectivity in random networks, in IEEE\/ACM Transactions on Networking25(2) (2017), 751\u2013764.","journal-title":"IEEE\/ACM Transactions on Networking"},{"key":"e_1_3_1_28_2","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/j.jda.2017.01.001","article-title":"Hybrid bellman ford dijkstra algorithm","volume":"42","author":"Dinitz Y.","year":"2017","unstructured":"DinitzY. and ItzhakR., Hybrid bellman ford dijkstra algorithm, J of Discrete Algorithms42 (2017), 35\u201344.","journal-title":"J of Discrete Algorithms"},{"issue":"3","key":"e_1_3_1_29_2","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1109\/TNSE.2016.2586750","article-title":"Efficient multistate route computation","volume":"3","author":"Rhodes D.L.","year":"2016","unstructured":"RhodesD.L., Efficient multistate route computation, in IEEE Transactions on Network Science and Engineering3(3) (2016), 171\u2013182.","journal-title":"IEEE Transactions on Network Science and Engineering"},{"issue":"3","key":"e_1_3_1_30_2","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1109\/TPDS.2016.2591011","article-title":"An optimal single-path routing algorithm in the datacenter network DPillar","volume":"28","author":"Erickson A.","year":"2017","unstructured":"EricksonA., KiasariA.E., NavaridasJ. and StewartI.A., An optimal single-path routing algorithm in the datacenter network DPillar, in IEEE Transactions on Parallel and Distributed Systems28(3) (2017), 689\u2013703.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"e_1_3_1_31_2","first-page":"565","volume-title":"Distributed approximation algorithms for weighted shortest paths","author":"Nanongkai D.","year":"2014","unstructured":"NanongkaiD., Distributed approximation algorithms for weighted shortest paths, In Proceedings of the forty-sixth annual ACM symposium on Theory of computing (STOC \u201914), ACM, New York, NY, USA, (2014), 565\u2013573."},{"key":"e_1_3_1_32_2","first-page":"77","article-title":"Parallel Implementation of MPEG-4Encoding over a Cluster of Workstations","author":"Karthik Sankar R.","year":"2005","unstructured":"Karthik SankarR., MoorthyS.K. and SomanK.P., Parallel Implementation of MPEG-4Encoding over a Cluster of Workstations, Advances in Systems, Computing Sciences and Software Engineering \u2013 Proceedings of SCSS (2005), pp. 77\u201382.","journal-title":"Advances in Systems, Computing Sciences and Software Engineering \u2013 Proceedings of SCSS"},{"key":"e_1_3_1_33_2","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/j.procs.2015.08.024","article-title":"ABDF integratable machine learning algorithms-map reduce implementation","volume":"58","author":"Sreeveni U.B.U.","year":"2015","unstructured":"SreeveniU.B.U. and SathyadevanS., ABDF integratable machine learning algorithms-map reduce implementation, Procedia Computer Science58 (2015), 297\u2013306.","journal-title":"Procedia Computer Science"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1101\/gr.1239303"}],"container-title":["Journal of Intelligent &amp; Fuzzy Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JIFS-169458","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/JIFS-169458","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JIFS-169458","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T09:38:35Z","timestamp":1777455515000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/JIFS-169458"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,22]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,3,22]]}},"alternative-id":["10.3233\/JIFS-169458"],"URL":"https:\/\/doi.org\/10.3233\/jifs-169458","relation":{},"ISSN":["1064-1246","1875-8967"],"issn-type":[{"value":"1064-1246","type":"print"},{"value":"1875-8967","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,22]]}}}