Prograph Based Analysis of Single Source Shortest Path Problem with Few Distinct Positive Lengths
Abstract
In this paper we propose an experimental study model S3P2 of a fast fully dynamic programming algorithm design technique in finite directed graphs with few distinct nonnegative real edge weights. The Bellman-Ford’s approach for shortest path problems has come out in various implementations. In this paper the approach once again is re-investigated with adjacency matrix selection in associate least running time. The model tests proposed algorithm against arbitrarily but positive valued weighted digraphs introducing notion of Prograph that speeds up finding the shortest path over previous implementations. Our experiments have established abstract results with the intention that the proposed algorithm can consistently dominate other existing algorithms for Single Source Shortest Path Problems. A comparison study is also shown among Dijkstra’s algorithm, Bellman-Ford algorithm, and our algorithm.
Keywords:
shortest path, negative weight cycle, weight matrix, variants, program-graph, SPL, dense network, scanned vertices, relaxationDownloads
References
J. B. Orlin, K. Madduri, K. Subramani, M. Williamson , “A faster algorithm for the single source shortest path problem with few distinct positive lengths”, Journal of Discrete Algorithms, Vol. 3, No. 1, pp. 1-10, 2009
A. W. Mohemmed, N. C. Sahoo, “Efficient Computation of Shortest Paths in Networks Using Particle Swarm Optimization and Noising Metaheuristics”, Discrete Dynamics in Nature and Society, Vol. 2007, No. 4, pp. 1-25, 2007 DOI: https://doi.org/10.1155/2007/27383
R. S. Pressman, Software Engineering – A Practioner’s Approach, Mc-Graw Hill, 2001
B. Bhowmik, “Dynamic Programming – Its Principles, Applications, Strengths, and Limitations”, International Journal of Engineering Science and Technology, Vol. 2, No. 9, pp. 4822–4826, 2010
F. B. Zahn, C. E. Noon, “Shortest path algorithms: an evaluation using real road networks”, Transportation Science, Vol. 32, No. 1, pp. 65–73, 1998 DOI: https://doi.org/10.1287/trsc.32.1.65
G. Desaulniers, F. Soumis, “An efficient algorithm to find a shortest path for a car-like robot”, IEEE Transactions on Robotics and Automation, Vol. 11, No. 6, pp. 819–828, 1995 DOI: https://doi.org/10.1109/70.478429
D. Eppstein, “Finding the k Shortest Paths”, 1997, available at http://www.ics.uci.edu/»eppstein/.
T. H. Coremen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, PHI, 2008
B. Bhowmik, “Studies on Dimultigraph and Prograph Based Applications of Graph Theory in Computer Science”, International Journal of Computer and Communication Technology, Vol. 1, No. 2, 3, 4, pp. 57-61, 2010
N. Deo, Graph Theory with Applications to Engineering and Computer Science, PHI, 2002
B. Bhowmik, Design and Analysis of Algorithms, S. K. Kataria and Sons, 2011
http://gabrielistrate.weebly.com
R. K. Ahuja, K. Mehlhorn, J. B. Orlin, R. E. Tarjan, “Faster Algorithms for the Shortest Path Problem”, Journal of the Association for Computing Machinery, Vol. 37, No. 2, pp. 213-223, 1990 DOI: https://doi.org/10.1145/77600.77615
M. H. Alsuwaiyel, Algorithms Design Techniques and Analysis, PHEI, 2003
D. Samanta, Classic Data Structures, PHI, 2010
E. Horowitz, S. Sahani, S. Rajasekaran, Fundamentals of Computer Algorithms, Golgotia, 1998
S. Baswana, T. Friedrich, S. Biswas, P. P. Kurur, B. Doerr, F. Neumann, “Computing Single Source Shortest Paths using Single-Objective Fitness Functions”, FOGA’09, January 9–11, 2009 DOI: https://doi.org/10.1145/1527125.1527134
http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/13-sssp.pdf
Farrukh Shehzad, Muhammad Akbar Ali Shah, “Evaluation of Shortest Paths in Road Network”, Pakistan Journal of Commerce and Social Sciences Vol. 3, pp. 67–79, 2009
Downloads
How to Cite
License
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
