Solution of Shortest Paths in Non-Euclidean Farey Graph with Floyd-Warshall Algorithm

Abstract

Algorithm applications on graphs are intensively researched. Graph theory systematizes complex and difficult problems and algorithms provide fast and clear solutions, which increases interest in the discipline. The Floyd-Warshall algorithm determines the shortest paths between all the vertices in a graph. In this paper, we consider the Floyd-Warshall algorithm on the Farey graph defined in a non-Euclidean hyperbolic space. A Farey graph with 15 edges and 9 vertices is constructed and the shortest paths from all vertices to other vertices are detected. By defining the weight between consecutive vertices, the shortest paths between the vertices are measured in terms of the number of steps.

Keywords

• Farey graph
• Floyd-Warshall algorithm
• non-Euclidean hyperbolic space

References

1. E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik, 1(1), 269–271, 1959.
2. R. Bellman, “On a routing problem”, Quarterly Applied Mathematics, 16, 87– 90, 1958.
3. P. D. Whiting and J.A. Hillier, “A method for finding the shortest route trough a road network”, Operations Research Quarterly, 11, 37-40, 1960.
4. P. E. Hart, N. J. Nilsson and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths”, IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107, 1968.
5. P. E. Hart, N. J. Nilsson and B. Raphael, “Correction to "A formal basis for the heuristic determination of minimum cost paths"", SIGART Newsletter, 28–29, 1972.
6. S. Dreyfus, “An appraisal of some shortest-path algorithms”, Operations Research, 17, 395-412, 1969. http://dx.doi.org/10.1287/opre.17.3.395
7. T. Veerarajan, Discrete Mathematics, with Graph Theory and Combinatorics, Mc Graw Hill India, 288 pages, 2006.
8. R. Diestel, Graph Theory, New York, Springer-Verlag Heidelberg, 322 pages, 2005.

9. K. Ruohonen, Graph Theory (Translation by Janne Tamminen, Kung-Chung Lee and Robert Piché), 114 pages, 2006.
10. C. C. Sims, “Graphs and finite permutation groups”, Mathematische Zeitschrift, 95,76-86, 1967.
11. G. A. Jones, D. Singerman and K. Wicks, “The modular group and generalized farey graphs”, London Mathematical Society Lecture Note Series, 160, 316-338, 1991.
12. A. H. Deger, M. Besenk ve B. O. Guler, “On suborbital graphs and related continued fractions”, Applied Mathematics and Computation, 218(3), 746-750, 2011.
13. A. H. Deger, “Relationships with the Fibonacci numbers and the special vertices of the suborbital graphs”, Gümüşhane University Journal of Science and Technology, 7,168−180, 2017.
14. A. H. Deger, “Vertices of paths of minimal lengths on suborbital graphs”, Filomat, 31(4), 913-923, 2017.
15. Ü. Akbaba, A. H. Değer and T. Berber, “An Algorıthm For The Vertıces On The Paths Of Mınımal Length In The Suborbıtal Graphs”, Proceedings of the 6th International Conference on Computational Mathematics and Engineering Sciences (CMES-2022) , 1(1), 250-255, 2022.
16. İ. Gökcan, “Application of Dijkstra Algorithm with Sequence F_m in F_(u,N)”, in Research&Reviews in Science and Mathematics-1, Gece Publishing, 2021, pp. 1-19.
17. P. M. Neumann, Finite Permutation Groups, Edge Coloured Graphs and Matrices, Topics in Group Theory and Computation, Curran M.P.J. (eds.), London, Academic Press, , 118 pages, 1977.
18. T. Tsukuzu, Finite Groups and Finite Geometries, Cambridge, Cambridge University Press, , 328 pages, 1982.