## 4 Design of Proposed Scheme: FAPR
### Algorithms and Formulation
#### 4.5.2 Optimized \(K\)-Shortest Paths Algorithm  
In the FAPR scheme, we use the concept of the \(K\)-shortest path algorithm to calculate backup paths for each link. The \(K\)-shortest path algorithm is a shortest path algorithm based on [PERSON]'s algorithm, which can find the total number of \(K\)-shortest paths from the starting point to the endpoint. The core idea of the \(K\)-shortest path algorithm is to use [PERSON]'s shortest path tree to continuously adjust the path of the tree until the \(K\)-shortest paths are found [46]. Since the \(K\)-shortest path algorithm needs to adjust the path multiple times, its time complexity is relatively high. As a result, FAPR optimizes the algorithm to increase computational efficiency through reducing the coselection rate among \(K\) paths. Based on the considerations mentioned above, we propose the optimized \(K\)-shortest path algorithm including the following three steps. If a binary heap is employed for optimization in Step 2 below, the time complexity of the algorithm can be reduced to \(O(kn(m+n)logn)\), where \(k\) is the number of backup paths of each link, \(m\) is the number of edges, and \(n\) is the number of nodes.  
Step 1 Pre-processing.  
The Floyd algorithm or Johnson algorithm can be used to calculate the shortest path between any two points in advance and store it in a matrix, especially for dense graphs. Whenever a shortest path from the starting point to the endpoint needs to be calculated, we just need to look up the matrix instead of recalculating, thus improving the efficiency of the algorithm.  
Step 2 Heap optimization.  
When executing [PERSON]'s algorithm, it is necessary to select a node closest to the starting point from the set of unprocessed nodes each time. If linear search is used, the time complexity is \(O(n^{2})\), where \(n\) is the number of nodes, and the time complexity is unacceptable for large-scale graphs. Therefore, we can use the heap data structure such as binary heap or Fibonacci heap to maintain the set of unprocessed nodes, and select the node closest to the starting point from the heap for processing. The time complexity can be reduced to \(O((m+n)logn)\) (using binary heap), where \(m\) is the number of edges and \(n\) is the number of nodes.  
Step 3 Pruning.  
In the \(K\)-shortest path algorithm, it is possible to record the length of the current path in the process of reverse search. If the length of the current path has already exceeded the longest path among the \(K\)-shortest paths, the search can be stopped immediately. By this means, the algorithm can avoid searching too many paths to improve the efficiency. In addition, the problem of overlapping among the calculated \(K\)-shortest paths is quite notable in some cases. To tackle this issue, we are inspired by the concepts found in [PERSON]'s algorithm. [PERSON]'s algorithm is famous for finding two disjoint shortest paths in a graph, achieved by adjusting the weights of the edges in the graph after identifying a shortest path. By incorporating this idea into the \(K\)-shortest path algorithm, we modify the weight of each edge after a shortest path is found, by adding a large constant. Consequently, when we run the [PERSON] algorithm again to find the next path, the newly calculated path tends to avoid edges used in the previous path, resulting in a significant reduction in the coselection rate.