# Optimal Routing in Urban Road Networks: A Graph-Based Approach Using [PERSON]'s Algorithm
## 3 Research Methodology for Determining Shortest Path
### Representation of the Traffic Network Using Graph Theory  
Taking into account the given analogy that it is possible to represent a real city traffic network with a series of nodes and interconnected paths, the postulates of graph theory can serve as a good basis for determining the shortest path. The definition of a graph implies that it consists of an ordered pair of elements \(G=(V,E)\) such that \(V(G)=V=O\) is a set of vertices or nodes (a non-empty set), and \(E(G)=E\subseteq\binom{V}{2}\) is a set of edges representing all two-element subsets of the set \(V\), connecting them [36]. The property of these ordered pairs of vertices and edges significant for identifying the desired path is reflected in the ability to \"walk\" through the graph, where a walk involves moving from one node to another along the edges connecting these pairs. Such movement where a node does not appear more than once is called a \"path\", and if a node is passed through more than once, a \"cycle\" occurs. The structure of a graph can be organized in such a way that various forms of node connectivity appear, including the so-called tree form, where there is only one path between any two nodes.  
From the standpoint of finding the shortest driving path, the existence of a path would be the most beneficial property of the graph, but the occurrence of cycles increases its length. Given that a graph mirrors the real city network system with conditions composed not only of simple geometry but also of traffic rules and an urban matrix that needs to be addressed, cycles may appear as part of the actual path. The occurrence of cycles can be influenced by the organization of traffic through the use of one-way streets that force the user into a specific directed path [37]. Such conditions must be imposed on the graph as well, leading to the definition of another significant property it supports, which is directionality.  
A walk through the graph depends on the characteristics of the edges along which the walk takes place. Collectively, all characteristics are combined into the concept of \"edge weight\". The simplest element that can constitute the weight is the length of an edge or the distance between two nodes connected by an edge. The mentioned speed-density-flow relationship can be one of the factors affecting the edge weight if the shortest travel time between given points in the network is sought, taking into account the overall traffic picture of the network. In such a consideration, in addition to the number of traffic participants, it would be necessary to define time obstacles, such as traffic lights, road works, or increased flow density, at certain times of the day, thereby further increasing the actual physical distance between nodes [38]. The condition for summing heterogeneous quantities is the prior normalization of their values to bring them to the same value. A common value that can be used is the time spent in traffic between two points, considering that the existence of each obstacle can be expressed as a time loss.