Abstract
Algorithms proposed in this article aim to find all edges on any smallest route connecting two nodes of a directed acyclic graph (DAG). However, for a DAG with N nodes, the number of routes possible connecting any two nodes can be exponential. Hence, it is unfeasible to compute all the routes to attain the smallest ones in the polynomial-time and eventually produce a set of all edges that contribute or make any of the smallest routes. This article presents all the existing approaches to solve the problem, and we propose a new technique to compute the required edges by taking advantage of parallel computing using the C++ OpenMP API by parallelizing one of the existing approaches. We present a step-by-step procedure to convert a sequential algorithm into a parallel algorithm by identifying the parallelizable tasks. We also took advantage of parallel Dijkstra’s by using the nested parallelism feature of OpenMP and presented a technique for deciding the optimal number of threads to run the tasks that involve unbounded parallelism. Using parallel computing, we could achieve a speedup of over 13% for a complete graph. The techniques proposed here are not confined only to this particular use case. However, these have a more extensive scope in dynamic programming (DP), graph theory, and counting problems pf.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ahire D, Jadhav O (2021) Commentary—methods to find all the edges on any of the shortest paths between two given nodes of a directed acyclic graph. Research Ideas And Outcomes, 7
Gross A (2012) Find all paths between two graph nodes. Stack Overflow. Retrieved 6 January 2021, from https://stackoverflow.com/a/9535898/7422352
DW (2015) Finding all paths between a set of vertices in a DAG. Comput Sci Stack Exchange (2015). Retrieved 11 February 2021, from https://cs.stackexchange.com/q/42043
Mancuso N (2015) Algorithm that finds the number of simple paths from s to t in G. Computer Science Stack Exchange. Retrieved 11 February 2021, from https://cs.stackexchange.com/a/3087/78734
Reitzig R (2019) Optimal algorithm to traverse all paths in the order of shortest path. Comput Sci Stack Exch. Retrieved 11 January 2021 from https://cs.stackexchange.com/q/19778
unkulunkulu (2013) Finding all shortest paths between two vertices. Stack Overflow. Retrieved 9 February 2021, from https://stackoverflow.com/a/16498391/7422352
Reitzig R (2019) Optimal algorithm to traverse all paths in the order of shortest path. Comput Sci Stack Exchange. Retrieved 23 February 2021, from https://cs.stackexchange.com/q/19778
Eppstein D (1998) Finding the k shortest paths. SIAM J Comput 28(2):652–673. https://doi.org/10.1137/s0097539795290477
Reitzig R (2017) Example of graph with exponential many s-t minpaths and min cut. Comput Sci Stack Exch. Retrieved 9 February 2021, from https://cs.stackexchange.com/q/33932
Willcock J (2011) Number of paths between two nodes in a DAG. Stack Overflow. Retrieved 11 February 2021, from https://stackoverflow.com/a/5164820/7422352
Draconis (2018) Finding all edges on any shortest path between two nodes. Comput Sci Stack Exchange. Retrieved 15 February 2021, from https://cs.stackexchange.com/q/93722
Israel R (2017) Find all edges not covered by a shortest path in an all-pairs shortest path over a subset of vertices. Math Overflow. Retrieved 15 February 2021, from https://mathoverflow.net/q/275681
Singh R (2015) How do I find all the edges that don’t lie on any of the shortest path? Stack Overflow. Retrieved 15 February 2021, from https://stackoverflow.com/q/32630422
DW (2015) How to find all shortest paths between two nodes in a weighted undirected graph? Comput Sci Stack Exch. Retrieved 17 February 2021, from https://cs.stackexchange.com/a/48658
DW (2018) Finding all edges on any shortest path between two nodes. Comp Sci Stack Exch. Retrieved 15 February 2021, from https://cs.stackexchange.com/q/93722
Sneyers J, Schrijvers T, Demoen B (2006). Dijkstra’s algorithm with fibonacci heaps: an executable description in CHR. In: Fink M, Tompits H, Woltran S (eds) 20th workshop on logic programming, Vienna, Austria, February 22–24, 2006, 1843-06-02. Vienna, Austria, February 22–24, 2006. Technische University at Wien, Austria INFSYS Research Report, 10pp. [In English]
Goel A, Kumar A, Rajan H (2019) Printing paths in Dijkstra’s shortest path algorithm. GeeksforGeeks. Retrieved 12 March 2021, from https://www.geeksforgeeks.org/printing-paths-dijkstras-shortest-path-algorithm/#:~:text=Value%20of%20parent%5Bv%5D%20for,path%20using%20below%20recursive%20function
Contributors to Wikimedia projects (2021) Dijkstra’s algorithm - Wikipedia. Wikimedia Foundation, Inc.. Retrieved 12 March 2021, from https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Dagum L, Menon R (1998) OpenMP: an industry standard API for shared-memory programming. IEEE Comput Sci Eng 5(1):46–55. https://doi.org/10.1109/99.660313
Khaldi D, Jouvelot P, Ancourt C, Irigoin F (2013) Task parallelism and data distribution: an overview of explicit parallel programming languages. Lang Comp Parallel Comput 174–189. https://doi.org/10.1007/978-3-642-37658-0_12
Greenlaw R, Hoover H, Ruzzo W (1995) Limits to parallel computation. Oxford University Press, Inc.198 Madison Ave. New York, NY, United States
Arjomandi E, Corneil D (1975) Parallel computations in graph theory. In: 16Th annual symposium on foundations of computer science (Sfcs 1975). https://doi.org/10.1109/sfcs.1975.24
Ye Z (2021) An implementation of parallelizing dijkstra’s algorithm. Presentation https://cse.buffalo.edu/faculty/miller/Courses/CSE633/Ye-Fall-2012-CSE633.pdf
Briggs J, Pennycook S, Fergusson J, Jäykkä J, Shellard E (2015) Cosmic microwave background analysis: nested parallelism in practice. High Performance Parallelism Pearls, pp 171–190. https://doi.org/10.1016/b978-0-12-803819-2.00024-0
Taylor C (2015) OpenMP: what is the benefit of nesting parallelizations? Stack Overflow. Retrieved 19 March 2021, from https://stackoverflow.com/a/4320422/7422352
Ahire D (2021) adeepak7/Code_to_demonstrate_sequential_execution_of_2_parallel_regions_created_using_OpenMP_API: First Release (Version v1.0). Zenodo. Retrieved 31 May 2021, from http://doi.org/10.5281/zenodo.4861948
Süß M, Leopold C (2008) Common mistakes in OpenMP and how to avoid them. Openmp Shared Memory Parallel Programming, pp 312–323. https://doi.org/10.1007/978-3-540-68555-5_26
Fürlinger K, Gerndt M Analyzing overheads and scalability characteristics of OpenMP applications. Lect Notes Comp Sci 39–51. https://doi.org/10.1007/978-3-540-71351-7_4
Ahire D (2020) C/Linux: how to find the perfect number of threads to use, to minimize the time of execution? Stack Overflow. Retrieved 25 March 2021, from https://stackoverflow.com/a/61121946/7422352
Pogrebinsky M (2021) Java multithreading, concurrency & performance optimization. Udemy. Retrieved 8 April 2020, from https://www.udemy.com/course/java-multithreading-concurrency-performance-optimization/
Bane M, Riley G (2002) Extended overhead analysis for OpenMP (Research Note). In: Proceedings of the 8th international euro-par conference on parallel processing (Euro-Par ’02). Springer-Verlag, Berlin, Heidelberg, pp 162–166
Pages.tacc.utexas.edu. (2021). Retrieved 26 March 2021, from https://pages.tacc.utexas.edu/~eijkhout/pcse/html/omp-basics.html
Iwainsky C, Shudler S, Calotoiu A, Strube A, Knobloch M, Bischof C, Wolf F (2015) How many threads will be too many? on the scalability of OpenMP implementations. Lect Notes Comput Sci 451-463. https://doi.org/10.1007/978-3-662-48096-0_35
Richards W (2004) The Zen of empirical research. Langara College, pp 45–58
Iliev H (2012) Why segmentation fault is happening in this openmp code? Stack Overlow. Retrived 23 April 2021, from https://stackoverflow.com/a/13266595/7422352
Ahire D, Bhandari S, Kamble K (2021) Finding the Kth max sum pair in an array of distinct elements using search space optimization. Innovations Comp Sci Eng 341–352. https://doi.org/10.1007/978-981-33-4543-0_37
Ahire D (2021) adeepak7/Fi6nding_all_edges_on_any_shortest_path_between_two_given_nodes_of_DAG_using_parallel_computing: First Release (Version v1.0). Zenodo. http://doi.org/10.5281/zenodo.4893226
Acknowledgements
We thank Dr. Medha A. Shah, HOD, CSE, WCE, Sangli, India for allowing us to use the WCE Deep Learning Server for computations.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Ahire, D., Kamble, K., Jadhav, O., Katakdhond, S. (2022). Finding All Edges on any Smallest Route Connecting Two Nodes of a Directed Acyclic Graph Using Parallel Computing. In: Saini, H.S., Sayal, R., Govardhan, A., Buyya, R. (eds) Innovations in Computer Science and Engineering. Lecture Notes in Networks and Systems, vol 385. Springer, Singapore. https://doi.org/10.1007/978-981-16-8987-1_73
Download citation
DOI: https://doi.org/10.1007/978-981-16-8987-1_73
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-16-8986-4
Online ISBN: 978-981-16-8987-1
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)