Finding the Anti-block Vital Node of a Shortest Path

Let G = (V, E) be an un-directed graph with non-negative edge weights and P(G) (s, t) be a shortest path between two nodes s and t where s, t, is an element of V(G). Suppose a package has been sent from s to t according to the route P(G) (s,t) in a network modelled by the graph G. It is usual that several nodes may be not available sometimes, and one failed node is only found when its previous node of the route P(G)(s,t) sends to it. In this scenario, an alternate route should be found which may lead to the increase the total length of the route. The paper discusses the problem of finding a node of the original route P(G)(s,t) whose removal results in the maximum increase of the total length. We present an algorithm that runs in O(vertical bar V vertical bar + vertical bar E vertical bar log vertical bar V vertical bar) time in the worst case. In addition, some future works are also given.