An Application of Bellman-Ford Algorithm in Hyperbolic Graph
TL;DR
The classical Bellman-Ford algorithm is examined and accepted in a manner that allows each edge to be traversed only once, and this algorithm is applied to the Farey graph F, defined on the hyperbolic plane and constructed Farey fractions.
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.