An Application of Bellman-Ford Algorithm in Hyperbolic Graph

Abstract

In this study, the classical Bellman-Ford algorithm, designed to operate on directed graphs with negative edge weights, is examined and accepted in a manner that allows each edge to be traversed only once. It is important to note that this study does not propose a new algorithm. Then, this algorithm is applied to the Farey graph F, defined on the hyperbolic plane  and constructed Farey fractions. The primary objective is to determine the shortest paths and their corresponding minimum weights from a designated source vertex to all other vertices in the graph. The Farey graph F is structured based on the orbits of the modular group , with edges determined by the group action. Each vertex represents a Farey fraction, and an edge exists between two vertices if the corresponding fractions are Farey neighbours. Edge weights are assigned in accordance with the modular group’s influence on the respective suborbital structures, resulting in a graph composed of bidirectional edges. Then, upon applying the Bellman-Ford algorithm to the graph F, it was observed that all vertices had reached minimum values. Furthermore, using the mediant operation, Farey graphs with edges of , and  were constructed. For each graph, numerical sequences were derived based on the minimum possible weights that vertices can attain. These sequences reflect the metric characteristics of graph expansions in the hyperbolic plane.

Keywords

• Bellman-Ford algorithm
• Farey graph
• Shortest path

References

1. [1]. Diestel, R. Graph Theory; Springer-Verlag Heidelberg: New York, 3. Edition, 2005.
2. [2]. Ruohonen, K. Graph Theory (Translation by Janne Tamminen, Kung-Chung Lee and Robert Piché);, 2013.
3. [3]. Gupta, C.B, Singh, S.R, Kumar, S. Advance Discrete Structure; I.K. International Publishing House Pvt. Ltd.: New Delhi, 2010.
4. [4]. Tremblay, J.P, Manohar, R. Discrete Mathematical Structures with Applications to Computer Science; Tata McGraw-Hill Edition: New Delhi, 2010.
5. [5]. Bal Gupta, S. Discrete Mathematics and Structures; University Science Press: New Delhi, 2008.
6. [6]. Das, M.K. Discrete Mathematical Structures for Computer Scientist and Engineers; Narosa Publishing House Pvt. Ltd.: New Delhi, 2008.
7. [7]. Veerarajan, T. Discrete Mathematics with Graph Theory and Combinatorics; Tata McGraw-Hill Edition: New Delhi, 2010.
8. [8]. Grimaldi, R.P. Discrete and Combinatorial Mathematics; Addision–Wesley, 1999.

9. [9]. Krishna Kumar, R. Discrete Mathematics; Laxmi Publications: New Delhi, 2006.
10. [10]. Somasundaram, R.M. Discrete Mathematical Structures; Prentice-Hall of India: New Delhi, 2007.
11. [11]. Aldous, J,M, Wilson, R.J. Graphs and Applications; Springer: London, 2000.
12. [12]. Cangül, İ.N. Graf Teori-I; Dora Basım-Yayın Dağıtım Ltd. Şti.: Bursa, 1. Baskı, 2017.
13. [13]. Sims, C.C. 1967. Graphs and finite permutation groups. Mathematische. Zeitschrift; 95, 76-86. (https://doi.org/10.1007/BF01117534)
14. [14]. Jones, G.A, Singerman, D, Wicks, K. 1991. The Modular group and generalized Farey graphs. London Mathematical Society Lecture Note Series; 160, 316-338. (https://doi.org/10.1017/CBO9780511661846.006)
15. [15]. Akbaş, M. 2001. On suborbital graphs for the Modular group, Bulletin of the London Mathematical Society, 33(6), 647-652. (https://doi.org/10.1112/S0024609301008311)
16. [16]. Deger, A.H. 2017. Vertices of Paths of Minimal Lengths on Suborbital Graphs, Filomat, 31(4), 913-923. (https://doi.org/10.2298/FIL1704913D)
17. [17]. Gökcan, İ. Application of Dijkstra Algorithm with Sequence F_m in F_(u,N), In: Akgül, H, Aksoy, A (ed) Research&Reviews in Science and Mathematics, Gece Publishing, 2021, 1-19.
18. [18]. Gökcan, İ. 2025. Solution of Shortest Paths in Non-Euclidean Farey Graph with Floyd-Warshall Algorithm. Süleyman Demirel University Faculty of Arts and Science Journal of Science; 20(1), 63-74. (https://doi.org/10.29233/sdufeffd.1591711)
19. [19]. Ahuja, R.K, Magnanti, T.L, Orlin, J.B, Network Flows Theory, Algorithms and Applications; Prentice-Hall: New Jersey, 1993.
20. [20]. Cormen, T.H, Leiserson, C.E, Rivest, R.L., Stein, C. Intruction to Algorithms; The MIT Press: United States, 2009.
21. [21]. Caprio, D.D, Ebrahimnejad, A, Alrezaamiri, H, Santos-Arteaga, F. J. 2022. A Novel Ant Colony Algorithm for Solving Shortest Path Problems with Fuzzy Arc Weights, Alexandria Engineering Journal, 61, 3403–3415. (https://doi.org/10.1016/j.aej.2021.08.058)
22. [22]. Yusuf, M. R, Nurwan, N, Wungguli, D, Yahya, L. Implementation of the Floyd-Warshall Algorithm and Bellman-Ford Algorithm to Determine the Shortest Path in the Distribution of LPG Gas, Gorontalo, Indonesia, 2023, 1-6. (https://doi.org/10.1051/e3sconf/202340003004)
23. [23]. Kannan, V, Appasamy, S. 2023. Employing the Bellman-Ford Algorithm with Score Functions to Address the Linear Diophantine Fuzzy Shortest Path Problem in Network Analysis, Mathematical Modelling of Engineering Problems; 10(5), 1884-1892. (https://doi.org/10.18280/mmep.100542)
24. [24]. Gajjar, K, Jha, A.V, Kumar, M, Lahiri, A. 2024. Reconfiguring Shortest Paths in Graphs, Algorithmica; 86, 3309–3338. (https://doi.org/10.1007/s00453-024-01263-y)