# Optimal Routing in Urban Road Networks: A Graph-Based Approach Using [PERSON]'s Algorithm
## 3 Research Methodology for Determining Shortest Path
### Algorithms for Determining the Shortest Path  
A graph by itself merely represents the domain for determining the shortest path in a network, but to concretize it, a series of defined rules must be applied to the graph, processing the elements with all their associated attributes and properties to form the output result. For this purpose, several algorithms have been developed to determine the desired path between two nodes. Determining the path is based on identifying all the distances between the nodes of the graph. To identify these distances, it is necessary to \"visit\" the neighboring nodes of a given node to establish the distance value. Visiting nodes is not a matter of personal choice but follows a certain order, depending on the scope and structure of the graph. According to the visiting order, a division of algorithms for graph exploration has been made into breadth-first search (BFS) and depth-first search (DFS). Breadth-first search (BFS) involves first identifying the root node of the search. In the first step, this would be the starting node from which the path begins, and given the cyclic nature of the algorithms, in each subsequent step, the root node would be the one examined in the previous step [39]. BFS involves determining all successors of a root node and assigning them the necessary attributes (distances, color, height, weight, etc. ), i.e., any value contained within the node. Only after resolving the first level of a search (when all successors of a node have been examined), do we proceed to examine the successors of all nodes that were examined in the previous step. From this, it follows that breadth-first search progresses by levels. [PERSON]'s Algorithm  
For the algorithm to be effectively used, the conditions met in the graph must be satisfactory. This refers to the weights of the graph edges, which must not have negative values [40]. From the perspective of use in urban traffic networks, it is not possible to include negative values in any way, as they represent segment lengths. Also, the application of the algorithm is not dependent on the direction of the edges. The principle of the algorithm classifies it as a greedy algorithm, meaning that, in the decision-making process at a given step, it makes a decision based on the best local solution currently. In the case of choosing the shortest path, this means that, from multiple paths from one node, it selects the one that is the shortest to the next node. Globally, such a chosen path might be the best solution at that moment, but there is a possibility that after selecting and moving to a new node where it ended, a locally long path follows, which is longer than those ignored in the previous step. Therefore, the algorithm is considered greedy, because it must find all solutions that satisfy local minima. As mentioned, it somewhat resembles breadth-first search (BFS) in some characteristics, but due to its inability to reach the desired solution in a single pass through all the nodes, it requires special additional steps to define the global minimum from the set of local minima. Chronology of the [PERSON]'s algorithm operation is best described through a series of steps [41]. Step 1  
The starting and ending nodes will be marked as nodes \(\mathbf{s}\) and \(\mathbf{t}\). Since the network consists of segments (individual paths or graph edges), it is necessary to assign an attribute to each node that indicates the total distance from \(\mathbf{s}\). The characteristic of this attribute is its variability, consisting of the sum of the lengths of individual edges. Variability results from the \"greediness\" of the algorithm, where certain \"errors\" in terms of local choices are allowed. In this step, the optimal solution is to assign an infinite distance value to each node (except the starting node), denoted as \(d^{-}(i)=\infty\).