# 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
Since the starting node does not need to calculate its distance, because it is not distant from itself, it will be assigned a value of 0 with the label \(\mathrm{d}^{+}(\mathbf{s})=0\), where individual labels represent:  
* (\(i\))--node label
* \({}^{-}\) sign indicating nodes whose attribute values are not final values, allowing for further updates in subsequent steps (variable label),
* \({}^{+}\) sign indicating nodes with updated attributes as final values, not subject to change in subsequent steps (immutable label). Alongside the symbols \(-\) and \(+\), it is necessary to associate concepts of tested and reached nodes, which will be further explained in Step 2. Step 2  
For Step 2, it is necessary to have a node with an immutable label. This means that it no longer undergoes attribute changes (length in the considered case). In the initial step, there is only one such node, which is the starting node \(\mathrm{d}^{+}(s)=0\). With each subsequent cycle of the algorithm, one new node will join this set. To include such a node, the following operations need to be performed in Step 2. The node being considered in the current cycle of the algorithm (which has an immutable label) will be marked with a general label (counter) \(i\). Based on its connectivity with other nodes in the network, a set A is formed consisting of nodes directly connected to the observed node \(i\) (its successors). The general label or counter of these nodes will be \(j\)and the final form of the set of successors will be \(j\in\text{A}_{i}\). For each \(j\) in set A, it is necessary to determine  
\[d(j)=\min\bigl{\{}d^{-}(j),d(i)+c_{ij}\bigr{\}} \tag{1}\]  
where  
\(d^{-}(j)\) is the variable attribute label (total distance from the starting node). In the initial step, it will be \(\infty\), while in each subsequent step, it takes the calculated value up to that point. \(d(i)\) is the immutable label and length from the node whose successors are currently being examined to the starting node. It has been mentioned that, in the initial step, this length is 0. \(c_{ij}\) is the distance between the node being examined and its successor. \(d(j)\) is the minimum value measured between the length from the starting node achieved up to the current step (attribute associated with the successor) and the length obtained by adding the attributes of the node being examined and its distance to the successor. Equation (1) will be printed as many times as a node has successors. Since the algorithm requires a local minimum, it will be necessary to find not only the minimum within one node but also the minimum among all successors, or all calculated \(d(j)\). \[d^{+}(j)=\min\{d(j)\} \tag{2}\]  
In Equation (2), the occurrence of an immutable label is noticeable, where the distance value is set as definitive, and the node where it is achieved will no longer be subject to the control process. All nodes that have been successors of any node and for which \(d(j)\) has been calculated are treated as examined. Only one of the examined nodes in one cycle of the algorithm will receive the label \(d^{+}(j)\), and such a node will be treated as examined and reached. Considering the above, it is possible to conclude the following:  
* As long as a node is in the set of examined nodes, its attributes may change. * The set of examined nodes includes all nodes that have been successors in any cycle of the algorithm for any node but have not changed their label to immutable. * All reached and examined nodes are sorted into a separate set S.
* Successors (set A) are sought only in relation to the last reached and examined node. For all nodes for which the value \(d(j)\) is calculated in expression (1) and does not satisfy expression (2), the value \(d(j)\) will be treated as \(d^{-}(j)\) in the next cycle of the algorithm. Step 2 defines the \"working\" part of the algorithm, while step 3 aims to determine the termination condition. The condition for this is that the node t is added to the set of reached and tested nodes S at the end of the queue.