# Optimal Routing in Urban Road Networks: A Graph-Based Approach Using [PERSON]'s Algorithm
## 4 Shortest Path Improvement by Applying [PERSON]'s Algorithm on a Sparse Counter Network
### Determining the Shortest Path in a Graph
After the selection, the examined node (coordinates) is added to the list of reached and examined nodes and then deleted from the list of examined nodes. These two lists, which cannot contain the same nodes, have the same structure. They consist of sublists, which include the following: **((coordinates of the node with the shortest distance) (coordinates of its predecessor) shortest distance). **  
This simplifies the reconstruction of the path from the last node to the first one, which is completed at the end of the algorithm. By setting the end node as the starting point, its predecessor and the distance to reach it are automatically identified in the list. Through an iterative process, the path continues back to the start node. By selecting the coordinates of the node with the smallest distance, followers are determined by searching the GRAPH_PT list for the required point. Since the coordinates of the points are given as the first item in the sublist in this list, the ASSOC command is sufficient to retrieve all followers with their corresponding attributes. Among these followers is the node from which the current one was reached, so it is not considered as a potential for further progression. Since the graph in question represents a traffic network, it is necessary to incorporate conditions that influence its operation. Knowing the followers is a necessary, but not sufficient, condition. Since the desired path is based on the shortest time spent driving, the type of maneuver (straight, left turn, right turn) is determined based on the position of the follower in relation to the incoming direction. If the achieved speed is equal to the maximum allowed speed, the assumption is that the flow is free of obstructions, and the maneuver will take the base time values, such as straight 3 s, right 5 s, and left 10 s [43; 44; 45; 46]. The maneuver time assumes a reduction in speed to an acceptable value for executing the maneuver and adjusting to the obstacle that the intersection itself represents. If the driving speed during the observed hour is lower than the maximum, the difference between the maximum allowed speed (V\({}_{\max}\)) and the minimum speed recorded on the counter (V\({}_{\rm min}\)) needs to be found. This interval is considered the operational range and is assigned boundary values of V\({}_{\rm max}\) = 0 and V\({}_{\rm min}\) = 1. Each examined speed will also have its value within the range of 0-1, which is multiplied by the base maneuver values and added to them. This covers the assumption that arriving at a lower speed means higher traffic congestion and the need for more time to execute the maneuver. To determine the type of maneuver, the following sign value was used:  
\[tg\frac{(\alpha-\beta)}{2} \tag{8}\]  
where:  
* \(\alpha\)--the angle formed by the positive \(X\)-axis and the line from the predecessor of the examined node to the examined node;
* \(\beta\)--the angle formed by the positive \(X\)-axis and the line from the examined node to the successor. A positive sign of the expression implies that the successor is on the right side, while a negative sign indicates that the successor is on the left, which determines the type of maneuver. This condition, with certain adjustments, is applied to intersections with both four and three directions, as well as to the junction of two lines that maintain the continuity of the street. After resolving the geometric conditions, the total travel time to each successor is calculated. The total time will be the sum of the time spent reaching the current point and the time needed to travel from the current point to the successor. The time from the current point to the successor is given by:  
\[t_{f}=t_{d}+t_{ll}+t_{m} \tag{9}\]  
where:  
* \(t_{d}\)--travel time along the line (street);
* \(t_{l1}\)--time lost if a traffic light is present;
* \(t_{m}\)--maneuver time (straight, right, left).