Suppose that metrics and are known for each link of the tree (lines 1 to 3). We first prove by contradiction that at least one end node of a backup path which minimizes is a leaf of . Suppose the end nodes and of a backup path that minimizes are known and that, by contradiction, is not a leaf of .
Let (see Figure 3.5). Then:

If no optimal backup path is found, then it is possible to extend Algorithm 1 to find a nearoptimal backup path. The extended algorithm (see Algorithm 2) proceeds as follows. As in Algorithm 1, metrics and are computed for all links of the tree and is preprocessed to speed up LCA computations in lines 1 to 4.
For any pair of nodes , the value of the metric does not depend on the order of the nodes of the pair, and is zero if both nodes of the pair are the same. Therefore, in a graph which contains nodes, there is a total number of possible pairs of end nodes for a backup path.
In lines 5 to 7 of Algorithm 2, metrics are computed for all pairs of nodes in the tree as defined above and the set of these metrics is ordered from the lowest to the highest in line 8. In lines 9 to 13, considering in turn each pair of nodes from the ordered set previously defined and starting from the pair of nodes which minimizes the set of metrics , a shortest path algorithm computes the backup path between the two nodes of the pair until a backup path is found. As with optimal backup paths, a nearoptimal backup path is not guaranteed to exist. More precisely, since Algorithm 2 considers in turn all possible pairs of nodes of the tree and tries to find a backup path between these two nodes until a backup path is found, if no nearoptimal backup path exists for tree then no backup path at all exists for the tree.
For instance, in the case where and , no optimal nor nearoptimal backup path can be found for .

When a node leaves (or joins) a multicast group, a certain number of nodes and links are removed from (or added to) the multicast routing tree. Consider the path in tree . Let be the first node on that is either a LER or has more than one child in . Therefore, when leaves (or joins) the multicast group, all links and nodes except of the path are removed from (or added to) the tree as shown in Figure 3.6. We denote by the modified tree and the modified metrics of . If is the value of metric for link in , then is the value of metric for link in . According to the definition of , if a topology modification occurs downstream of with regards to , then the values of the metrics for links upstream of with regards to only are changed.
Algorithm 3 proceeds as follows. First, metrics are recomputed for links on the path between nodes and in lines 1 to 3. Then, in lines 4 to 6, the metrics are updated for all pairs of nodes of tree . Let be the new value of the metric taken between nodes and in tree . It is possible to compute in using the value of in and therefore avoid doing all computations again. For instance, if Definition 3 is used to compute the metrics and , then, when leaves the group:
=  
=  
+  
+ . 
Since all nodes of are removed from the tree when leaves the group, neither nor can be between and . Therefore:
If we call the first link on the path from to , then the expression above can be further simplified:
and thus:
=  
+  
+ . 
Furthermore:
=  
=  
+  
+  
=  
+  
+ 
Consequently:
Similar expressions are available in the case where joins a group. Therefore, instead of completely recomputing all metrics , it is possible to compute the new metrics by substracting from the old metrics a value of the metric and adding products for links of a path of a tree. When all metrics are updated, a backup path is computed in lines 7 to 8 using a shortest path algorithm between the two nodes of the pair which maximizes the set of all metrics as in Algorithm 1.
Algorithm 3 is able to handle the modification of a multicast routing tree incurred by any leaving or joining node. In the case where a node is leaving the multicast group, and where this node is not an end node of the backup path computed for the tree topology prior to the modification, a trivial alternative to Algorithm 3 is available to handle the modification. This alternative merely consists in leaving the formerly computed backup path unchanged. Obviously, the unchanged backup path is not guaranteed to be optimal anymore, but no further computation is required to update the backup path. Therefore, to reduce the amount of computations required to update a backup path on a tree topology change, it is possible to set a threshold on the number of modifications of the multicast routing tree and not update the backup path until this threshold is reached. Then, Algorithm 3 can be used to recompute the backup path.