## 4 Algorithm Analysis
In an ideal optimal state, the backup path should not share any nodes or links with the optimal path. This ensures that in the event of optimal path failure, the integrity of the backup path remains unaffected. ### Introduction to the Algorithm

In the topology graph \(G=(V,E,W)\), where \(s\) represents the source node and \(d\) denotes the destination node, the MCD-BP algorithm is implemented through the following steps: (1) Determine the most optimal path, denoted as \(sp(s,d)\), from the source node \(s\) to the destination node \(d\). (2) Assign the optimal path to the backup path, denoted as \(sp(s,d)=sp^{\prime}(s,d)\). Check for any intersections between \(sp(s,d)\) and \(sp^{\prime}(s,d)\). If no intersection is found, then \(sp^{\prime}(s,d)\) is the definitive backup path. However, if an intersection

Figure 2: Example of a topology diagram. exists, move on to the subsequent step. (3) Employ the link deletion rules stated above to remove the links at the intersection, then recalculate the backup path. Continue this iterative process of deletion until a backup path with the lowest degree of intersection is ultimately achieved. The theorems inherent to the algorithm are detailed as follows:

**Theorem 5**. : _(Connectivity Iteration Guarantee of the MCD-BP Algorithm). Within the network framework of the MCD-BP algorithm, it is imperative that any backup path, tracing from any source node to any destination node, be iteratively expunged in accordance with the link deletion rule. This is to ensure the uninterrupted connectivity of the path._

The MCD-BP algorithm necessitates an understanding of a key function--the Del_edge function. This function plays a pivotal role in iteratively deleting links within the intersection degree set \(K\) while concurrently adhering to the aforementioned theorem. The following presents the pseudocode segment of this particular function. The Del_edge function Algorithm 2 takes as input the set \(K\) and the possible backup path \(sp^{\prime}(s,d)\), and it outputs the potential backup paths. On line 2 of the function, a preliminary variable i is initialized to 0. We next impose a condition on \(sp^{\prime}(s,d)\), leading to the invocation of a loop algorithm when the backup path \(sp^{\prime}(s,d)\) is null. This loop algorithm yields a new graph \(G^{\prime\prime}\), derived by removing the edge proximate to the source point within cross-degree \(K\) of the initial graph \(G\). Utilizing the newly constructed graph \(G^{\prime\prime}\), compute the shortest path from node \(s\) to node \(d\), designated as the backup path \(sp^{\prime}(s,d)\). In the event that the set \(K\) is found to be vacant, proceed by returning the extant backup path \(sp^{\prime}(s,d)\) and subsequently terminate the function. Upon completion of the function, the last computed backup path \(sp^{\prime}(s,d)\) will be returned. Conversely, if the set \(K\) is not devoid of elements, repeat execution. ```
input :\(K,sp^{\prime}(s,d)\) output :Possible backup path \(sp^{\prime}(s,d)\) Function\(Del\_edge(K,sp^{\prime}(s,d))\):
1\(i\gets 0\) while\(sp^{\prime}(s,d)=\emptyset\)do
2 delete \(K[i++]\)
3\(G^{\prime\prime}\gets G/K[i++]\)
4 compute \(sp^{\prime}(s,d)\) in \(G\)
5 if\(K==\emptyset\)then
6 return\(sp^{\prime}(s,d)\)
7
8 end if
9
10 end while return\(sp^{\prime}(s,d)\)
```

**Algorithm 2**Del_edge function

Next, we will introduce the MCD-BP algorithm as follows:

In the pseudocode for MCD-BP Algorithm 3, the destination node is denoted as \(d\), the input topology graph as \(G=(V,E,W)\), and the output backup path as \(bp(s,d)\). Initially, the algorithm creates an empty set \(K\) to store the intersection degree (lines 1-2). It then computes the shortest path \(sp(s,d)\) using the Dijkstra algorithm. Concurrently, it initializes a potential backup path \(sp^{\prime}(s,d)\) as an empty set. The algorithm initiates the loop at line 3, where it assigns the most optimal path \(sp(s,d)\) to \(sp^{\prime}(s,d)\).