## 2 Methods
### Improved A* Algorithm for the Path Analysis of Restricted Networks
#### 2.1.3 Transfer Matrix
During the data pre-processing stage, the number of transfers, time, and cost between any two points in the restricted network can be pre-stored in an array list, which makes it easy to obtain the estimated cost \(H(N)\) for reaching the ending point \(D\) from any point \(N\). Thus, the price \(F(N)\), including the transfer number, travel time, and travel costs, paid from the starting node \(O\) to the ending point \(D\) through any point \(N\), can be efficiently calculated in real time during the execution of the algorithm. The main steps of the improved A* algorithm of path analysis for restricted networks (Figure 4) are outlined as follows:  
1. Load data for restricted networks, and calculate the \(G(N)\), \(H(N)\), and \(F(N)\) values of the starting node \(O\), which are respectively represented by \(g\), \(h\), and \(f\). According to the previous analysis, \(g_{0}\) = \(\begin{cases}0\text{ },h_{0}=\left\{ \begin{array}{ll}Q_{od}\\ T_{od}\text{ },\text{ }f_{0}=g_{0}+h_{0}\text{, where }Q_{od}\text{, }T_{od}\text{, and }C_{od}\text{ are }\\ 0\end{array} \right.\) the paid cost from \(O\) to \(D\). Furthermore, the \(O\) node is added into the array ExNodes. 2. If the array ExNodes is not empty, select node \(M\) with the minimum \(f\) value from ExNodes, and expand node \(M\). The minimum value of \(f\) is calculated according to the following rules. First, if the values of \(Q_{od}\) are not equal, comparing the values  
Figure 4: Flowchart of the improved A* algorithm for path analysis of restricted networks. of \(Q_{\alpha d}\), the minimum value of \(f\) is that the smallest \(Q_{\alpha d}\) belongs to \(f\). If values of \(Q_{\alpha d}\) are equal, comparing the values of \(T_{\alpha d}\), the minimum value of \(f\) is that the smallest \(T_{\alpha d}\) belongs to \(f\). If the values of \(T_{\alpha d}\) are equal too, comparing the values of \(C_{\alpha d}\), the minimum value of \(f\) is that the smallest \(C_{\alpha d}\) belongs to \(f\). 3. The expansion steps of node \(M\) are as follows. 1. Search for nodes adjacent to \(M\), and calculate their corresponding \(g\), \(h\), and \(f\) values. The method how to search for nodes adjacent to \(M\) is to search for nodes adjacent to \(M\) via the line topology connection. For any expanded nodes \(E\) of \(M\), if \(E\) and \(M\) are on the same line, then \(Q_{\alpha e}=Q_{\alpha m}\); otherwise, \[Q_{\alpha e}=Q_{\alpha m}+1.\] Moreover, \(h_{e}= \begin{cases}Q_{\alpha d}\\ T_{\alpha d}\\ C_{\alpha d}\end{cases} .\] 2. Evaluate whether node \(E\) coincides with the nodes in the current array ExNodes. If node \(E\) coincides with node \(P\) in ExNodes, \(Q_{\alpha e}<Q_{\alpha p}\), node \(P\) in ExNodes is replaced with node \(E\). If \(Q_{\alpha e}>Q_{\alpha p}\), node \(E\) is deleted. If \(Q_{\alpha e}=Q_{\alpha p}\), comparing the values of \(T\), if \(T_{\alpha e}<T_{\alpha p}\), node \(P\) in Exnodes is replaced with node \(E\). If \(T_{\alpha e}>T_{\alpha p}\), node \(E\) is deleted. If \(T_{\alpha e}=T_{\alpha p}\)_too_, comparing the values of \(C\), if \(C_{\alpha e}<C_{\alpha p}\), node \(P\) in Exnodes is replaced with node \(E\). If \(C_{\alpha e}>C_{\alpha p}\), node \(E\) is deleted. 3. If there is no coincidence node between \(E\) and that in ExNodes, the status of node \(E\) is recorded and added into ExNodes. 4. After the expansion of node \(M\), the best path from \(O\) to \(M\) is recorded. 5. Judge whether node \(M\) is the ending point \(D\). If \(M\) is not the ending point, continue to select the node \(M\) with the minimum value \(f\) from ExNodes to expand, and repeat steps 2-4 until it reaches the ending point \(D\). 6. If \(M\) is the ending point \(D\), output the travel plan from \(O\) to \(D\), and the algorithm ends. The A* algorithm's performance is affected by two main factors: determining how to sort the sequence of nodes to be expanded and checking the coincidence problem for each generated sub-node.