Open AccessPrograph Based Analysis of Single Source Shortest Path Problem with Few Distinct Positive Lengths
Author(s) -
Biswajit Bhowmik,
Srijit Chowdhury
Publication year - 2011
Publication title -
engineering, technology and applied science research/engineering, technology and applied science research
Language(s) - English
Resource type - Journals
eISSN - 2241-4487
pISSN - 1792-8036
DOI - 10.48084/etasr.41
Subject(s) - shortest path problem , dijkstra's algorithm , yen's algorithm , k shortest path routing , shortest path faster algorithm , adjacency matrix , implementation , computer science , path (computing) , algorithm , mathematical optimization , adjacency list , graph traversal , dynamic programming , suurballe's algorithm , enhanced data rates for gsm evolution , longest path problem , mathematics , graph , theoretical computer science , tree traversal , artificial intelligence , programming language
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.