# An Arch-Bridge Topology-Based Expressway Network Structure and Automatic Generation
## 3 Methodology
### Automatic Generation of Expressway Network Topology
#### 3.2.2 Candidate Topology Set Optimization
[PERSON]'s method is a shortest-path method proposed by Dutch computer scientist [PERSON] in 1959 [60]. It solves the shortest path problem from one vertex to all other vertices and is exactly the problem we need to solve in a non-negative weighted graph. Therefore, this section will use [PERSON]'s method to obtain the shortest path between two gantry nodes from the distance-weighted graph \(\mathbf{\hat{G}}_{\text{D}}\)=\(<G\), \(\epsilon\mathbf{E}\), \(D>\). The main feature of [PERSON]'s method is to start from the starting point and use the greedy strategy to traverse the adjacent nodes of the vertex closest to the starting point and not visit until the endpoint is reached. The specific steps are as follows:  
Step 1: Calculate the distances \(\text{D}=\left\{d\left(\mathbf{ce_{ij}}\right)\right\},i=1,2,3,\ldots,n\) for all candidate edge sets \(\mathbf{c}\mathbf{E}\), and construct an expressway network distance-weighted graph \(\mathbf{\hat{G}}_{\text{D}}\)=\(<G\), \(\epsilon\mathbf{E}\), \(D>\);  
Step 2: Set the starting point \(o\) and the ending point \(d\), mark the starting point, and set all other nodes as unmarked. Let \(k=o\), \(l_{oo}=0\), \(l_{oj}=+\infty\), and \(p=[]\) be the predecessor array;  
Step 3: Search for the node \(j\) directly connected to node \(k\) in the set of all unmarked nodes and calculate and update as follows:  
\[l_{oj}=\min\left\{l_{oj},l_{ok}+d_{kj}\right\} \tag{7}\]  
If \(l_{oj}\) is updated, set the predecessor of node \(j\) to \(k\) and update the predecessor array \(p\);  
Step 4: Obtain the node \(j^{*}\) in the set \(J\) of all unmarked nodes that is closest to the starting point \(o\):  
\[j^{*}=\underset{j\in J}{\text{argmin}}\left(l_{oj}\right) \tag{8}\]  
Step 5: Mark \(j^{*}\). If all nodes have been marked, the method exits; otherwise, update \(k=j^{*}\) and go to Step 3. Finally, obtain the \(path=\langle g_{k},g_{k+1},\ldots,g_{n}\rangle,g_{k}=g_{i},g_{n}=g_{j}\); the total accumulated distance of this route is \(d_{path}=\sum_{k=1}^{n-1}d\left(\mathbf{ce_{k(k+1)}}\right)\). Therefore, in the case of missing transactions, the following constraint can be designed:  
\[\epsilon\mathbf{E}=\left\{\mathbf{ce_{ij}}\middle|d_{path^{*}}^{\mathbf{ce_{ij}}}=d\left( \mathbf{ce_{ij}}\right)\wedge\mathbf{ce_{ij}}\in\mathbf{c}\mathbf{E}\right\} \tag{9}\]  
(d) Opposite Topology Optimization  
According to different opposite gantry configurations, erroneous transactions can be classified into three types:\(\left\langle\xi_{i},g^{\prime}_{i}\right\rangle\) or \(\left\langle g^{\prime}_{i},g_{i}\right\rangle\): erroneous transactions with the bidirectional gantry itself;
2\(\left\langle\xi_{i},g^{\prime}_{i+1}\right\rangle\) or \(\left\langle g^{\prime}_{i},g_{i+1}\right\rangle\): erroneous transactions with the bidirectional gantry of the next gantry \(g_{i+1}\), directly connected in the same direction as \(g_{i}\);
3\(\left\langle\xi_{i},g^{\prime}_{i+1}\right\rangle\) or \(\left\langle g^{\prime}_{i},g_{i+n}\right\rangle\): erroneous transactions with the opposite gantry \(g_{i}\) of the \(n\)th (\(n\geq 2\)) gantry \(g_{i+n}\) in the same direction as the gantry \(g_{i}\). Except for the first case, the second and third cases involve not only erroneous but also missing transactions, which is called the erroneous and missing phenomenon. For example, in \(\left\langle g_{1},g^{\prime}_{n}\right\rangle\), the erroneous transaction gantry is \(g^{\prime}_{n}\), and the missing transaction gantries are \(\left\langle g_{2},\ldots,g_{n+1}\right\rangle\). Of course, the first case involves mutually exclusive gantry node pairs \(\left(g^{\prime\prime}_{i}\Leftrightarrow g^{\prime\prime}_{i}\right)\), and the topology candidate edges formed by these gantry node pairs can be directly removed from the topology candidate edge set \(\epsilon E\).