Finding the Optimal Shortest Path Tree with Respect to Single Link Failure Recovery
Yueping Li, Zhe Nie, Xiaohong Zhou · 2008
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 Ts={e1, e2,hellip, en-1} rooted at s satisfies the path from s to uiin Tsis a shortest path in G, where ei=(ui, vi) and ui=parent(vi). Let |PG(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 maxforalle=(x,y)isinE(P)|PG\e(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|2log|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.