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

B. Bhowmik, S. Nag Chowdhury

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

Full Text:

PDF

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

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

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

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

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

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




eISSN: 1792-8036     pISSN: 2241-4487