Identification of shortest path with Dijkstra’s algorithm through the distribution function analysis of flow and connectivity in non-directed graphs

P. Kamal Devi

doi:10.26637/MJM0804/0180

Abstract

A non-directed graph is one type graph and these nodes are connected by non-directed arcs. A non-directed arc is an edge that has no arrow. Both ends of a non-directed arc are equivalent-there is no head tail. Therefore, this paper represents an edge in a non-directed graph as a set rather than an ordered pair which is assigned with weighted path. So it is important to calculate to find the shortest path in assigned graphs. Dijkstra algorithm is one of the familiar methods to find shortest paths from point to another point in a graph. It is also known as single source shortest path algorithm and which is applied only on positive weights. This paper proposes a new scheme for computing the shortest paths on non-directed graphs with distributed function analysis. It creates a linear size structure that facilitates single source shortest path computations in $o(m \log a)$ time, where $a=\alpha(m, n)$ is the slowly growing inverse - Ackermann function, $p$ the number of vertices and $q$ the number of edges. This algorithm infers ne bounds on both the all pairs and single source shortest paths problems. To resolve the all pairs problem in $o(m n \log \alpha(m, n))$ time and, if the ratio between the maximum and minimum edge length is constrained by $n^{(\log n)^{o(1)}}$ These results express the better performance of Dijkstra algorithm in undirected graphs.

Keywords:

Non-directed graphs, shortest paths, Dijkstra algorithm, distributed function analysis, minimum edge length

Mathematics Subject Classification:

Mathematics

Authors Imprint References Funding Related Articles Downloads

P. Kamal Devi Department of Mathematics, Pioneer Kumaraswamy College, Nagercoil-629003, Tamil Nadu, India. Affiliated to Manonmaniam Sundaranar University, Abishekapatti-Tirunelveli-627012.

Pages: 2346-2351
Date Published: 01-10-2020
Vol. 8 No. 04 (2020): Malaya Journal of Matematik (MJM)

A. Bargiela and W. Pedrycz, Toward a theory of granular computing for human-centered information processing, IEEE Transactions on Fuzzy Systems, 16(2)(2008), 320330. DOI: https://doi.org/10.1109/TFUZZ.2007.905912

Y. Gao, Shortest path problem with uncertain arc lengths, Computers and Mathematics with Applications, 62(6)(2011), 2591-2600. DOI: https://doi.org/10.1016/j.camwa.2011.07.058

M.T. Hajiaghayi, R.D. Kleinberg, H. Racke, T. Lighton, Oblivious routing on node- capacitated and directed graphs, ACM Transactions on Algorithms, 3(4)(2007), 51-es. DOI: https://doi.org/10.1145/1290672.1290688

P. Kamal Devi, G. Eswara Prasad, V.S. Mathu Suresh, Application of distribution function analysis of flow and connectivity in non-directed graphs for Shortest path findings through the mathematical modeling of Floyd's algorithm, International Journal of Advanced Research in Engineering and Managemant, 3(10)(2017), 21-28.

${ }^{[5]}$ U.V. Kayarkar, R.A. Puranik, Algorithms to find minimal path in networks using graph theory, 2008.

D.E. Knuth, A generalization of Dijkstra's algorithm, Information Processing Letters, 6(1)(1977), 1-5. DOI: https://doi.org/10.1016/0020-0190(77)90002-3

G.A. Pavlopoulos, M. Secrier, C.N. Moschopoulos, T.G. Soldatos, S. Kossida, J. Aerts, P.G. Bagos, Using graph theory to analyze biological networks, Bio Data Mining, 4(1)(2011), 10-19. DOI: https://doi.org/10.1186/1756-0381-4-10

S. Pettie, V. Ramachandran, A shortest path algorithm for real weighted undirected graphs, SIAM. Comput., $34(6)(2005), 1398-1431$. DOI: https://doi.org/10.1137/S0097539702419650

H. Selim, J. Zhan, Towards shortest path identification on large networks, Journal of Big Data, 3(1)(2016), 10-20. DOI: https://doi.org/10.1186/s40537-016-0042-7

C. Sommer, Shortest-path queries in static networks, ACM Computing Surveys, 46(4)(2014), 45-50. DOI: https://doi.org/10.1145/2530531