Prograph Based Analysis of Single Source Shortest Path Problem with Few Distinct Positive Lengths

  • B. Bhowmik Department of Computer Science & Engineering, Bengal College of Engineering and Technology, India
  • S. Nag Chowdhury Department of Computer Science & Engineering, Bengal College of Engineering and Technology, India

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, relaxation

Downloads

Download data is not yet available.

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

Metrics

Abstract Views: 285
PDF Downloads: 77

Metrics Information
Bookmark and Share