# 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
### Creating One-Way Streets  
The use of one-way streets in urban traffic organization is inevitable, either for the rationalization of space usage or to increase functionality. Therefore, this movement model needs to be established when selecting the shortest path in a graph. [PERSON]'s algorithm can also be applied to directed graphs, which is a realistic representation of a one-way street. Since a city is never entirely made up of one-way streets, the graph will represent a combination of both two-way and one-way traffic. A directed graph implies that movement is possible from node \(i\) to node \(i+1\), but movement from node \(i+1\) back to node \(\mathbf{i}\) is prohibited. This principle must be adopted through the modification of the algorithm, restricting the nodes that can be visited based on the node from which the movement originates. Since the entire network within the AutoCAD program is created from LINE entities, and each line has its start and end defined by group codes 10 and 11, it is impossible to establish a sequence of lines that would orient coordinates in the desired direction of movement. Additionally, it is possible that, at some nodes, only the ends of lines meet (with coordinates containing only group code 11) or the starts (the group code for all lines departing from the node is 10). This makes selection based on group code practically impossible. The problem is overcome by using polyline entities, as they consist of a series of interconnected segments, where the end of one segment is simultaneously the start of another, allowing the definition of coordinates along which movement is possible or restricted. To edit this base segment, AutoLISP code 02--one-way street Dijkstra has been created. The idea of this code is based on the fact that a polyline is drawn along the line segment where one-way traffic occurs, starting where traffic enters the street and ending where it exits. This way, the allowed direction of vehicle movement matches the sequence of coordinates (from first to last) that make up the polyline entity. Drawing individual polyline entities in AutoCAD is inefficient, as each vertex along the segment needs to be selected. To save time, the 02--one-way street Dijkstra code uses the concept of the shortest path between the starting and ending points of the street. If the part of the city with the one-way street is considered a graph, it is possible to find the shortest path between the start and end points of the one-way street. The code prompts the user to select the area (LINE entities) containing the requested segment, as well as the starting and ending points. The embedded Dijkstra algorithm searches for the shortest path between the specified nodes, considering only the edge lengths as weights. The speed of movement is not used as a parameter, as only the geometric condition of the street's shape needs to be respected. Depending on the geometry of the requested street and the number of selected lines, the calculated path may deviate from the one that should represent the one-way street (Figure 4). If the actual one-way street is marked as 1-2-3, the algorithm will give the shortest path marked in dark blue (1-3). For this reason, the user is presented with an option through a command line query to either accept the proposed path (command: accept the street) or correct it (command: exclude the edge at the first wrong turn). The correction involves selecting the segment (LINE) at the point where the proposed path first deviates from the correct one. Figure 4: One-way street definition. In Figure 4, this would mean selecting the brown line that exits from node 1 and goes towards node 3. A reselection of the area (to reform the graph) is not required; instead, the selected incorrect street is eliminated from the existing graph, and the calculation is repeated without it. The correction can be performed an unlimited number of times until complete alignment between the real state on the ground and the presentation in the graph is achieved (cyan line 1-2-3 in the figure).