Finding the Optimal Shortest Path Tree with Respect to Single Link Failure Recovery

This paper investigates the shortest paths tree problem taking single link failure into account. Let G be a graph modeled by network with vertex set V and edge set E. Given a specified vertex s. A shortest paths tree T_s={e₁, e₂, _hellip, e_n-1} rooted at s satisfies the path from s to u_i in T_s is a shortest path in G, where e_i=(u_i, v_i) and u_i=parent(v_i). Let |P_G(s,t)| be the cost of the shortest (s, t)-path in graph G. A shortest (s,t)-path P is optimal with respect to single link failure if max_{foralle=(x,y)isinE(P)}|P_Ge(x,t)| is minimum among all the shortest (s,t)-paths. A shortest paths tree is optimal if it consists of optimal shortest paths. We present an algorithm that takes O(|V| |E|+|V|²log|V|) time to build the shortest paths tree. Our result is applicable to the route design in the communication network when single link failure is considered.