# 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
As long as the condition from step 3 is not satisfied, step 2 will be repeated. The goal of the algorithm is finding the shortest path, and the previous three steps do not provide a unique solution due to the earlier mentioned characteristic of the \"greedy\" algorithm. Since local minima are sought in each step, step 4 will serve to unify them into a global one. The idea is based on defining a path starting from its end, i.e., node t, which was last added and marked as \(d^{+}(t)\). During the exploration, all network nodes received either an immutable (\(d^{+}(j)\)) or mutable (\(d^{-}(j)\)) label, so there is distance information from the initial node for each of them. Among all these nodes, it is necessary to find a node with an immutable label, which through step 4 is defined as node jk and its distance as \(d^{+}(j_{k})\). The characteristics of the selected node should match the following equation:  
\[d^{+}(t)-d^{+}(j_{k})=c_{j_{k},t} \tag{3}\]  
Equation (3) defines that the difference in attribute values between the terminal node and the node from which the terminal node was accessed must be equal to the actual distance between them (\(c_{j_{k},t}\)). Besides node \(j_{k}\), there may be other nodes connected to \(t\), which will be denoted as \(q_{r}\). For all of them, the expression holds, as follows:  
\[d^{+}(t)-d(q_{r})\leq c_{q,t} \tag{4}\]  
This demonstrates that the difference in attributes between the terminal node and each of its neighbors (except \(j_{k}\)) is not equal to the physical distance between them. This unequivocally determines the node that lies on the actual path preceding the terminal node. This approach needs to be repeated for all other nodes, so for finding predecessors to node \(j_{k}\), the following will apply:  
\[d^{+}(j_{k})-d^{+}(j_{k-1})=c_{j_{k-1},j_{k}} \tag{5}\]  
To put it simply, node \(s\) will be accessed:  
\[d^{+}(j_{1})-d^{+}(j_{s})=c_{j_{1},s} \tag{6}\]  
The sequence obtained \(s,j_{1},j_{2},\ldots,j_{k-1},j_{k}\), \(t\) represents the actual shortest path between the initial and terminal nodes. By summing the lengths of the edges between the nodes in the sequence, the same value as the immutable label of node \(t\) will be obtained, as follows:  
\[d^{+}(t)=c_{s,j_{1}}+c_{j_{1},j_{2}}+...c_{j_{k},t} \tag{7}\]  
It is important to note that [PERSON]'s algorithm does not support the use of negative weights during computation, meaning in this case, negative time. Given the characteristics of the AutoLISP programming language, the algorithm has been partially modified and adapted for more efficient operation. Since a node must be examined before it is reached, its value needs to be changed from the maximum cost \(\infty\) to a finite value (\(d^{-}(j)\)). The large number of points in the list would require constant updating with the element replacement option, which significantly slows down the process. Therefore, in addition to the list of reached and examined nodes (\(d^{+}(j)\)), which is mandatory, a list of only examined nodes (\(d^{-}(j)\)) has been created. For each node, when calculating the cost value, its presence in both the examined list and the reached and examined list is checked. If the node is not present in either, it means that it has not been visited up to the current step and will surely be added to the examined list. The second modification concerns step 4. Instead of finding the lengths corresponding to the predecessor node on the path from the end node to the starting node, the reached and examined nodes list is sorted in pairs consisting of the reached and examined node in the current step, as well as its predecessor, showing where the current node was accessed from. In this way, by moving from the last node, its predecessor is found until the starting node is reached, thus completing the path definition.