An Optimized All pair Shortest Paths Algorithm

In this paper, we present an algorithm to compute all pairs optimized shortest paths in an unweighted and undirected graph with some additive error of at most 2.This algorithm can be extended for weighted graph also but it will not work for directed graph due to absence of commutative property. The algorithm runs in O(n5n) times, where n is the number of vertices in the graph. This algorithm is much simpler than the existing algorithms. A study of upper bounds on the size of a maximal independent set of such graphs has been performed.