Abstract—In this paper, an all pairs optimized shortest path algorithm is presented for 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 run time of the algorithm is of order Ο(n5/2), where n is the number of vertices present 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 also been discussed.

Index Terms—Additive Error, Commutative, Multi-plicative Error, Optimized.

P K Singh is with the Computer Science and engineering Department, MMM Engineering College, Gorakhpur (Uttar Pradesh), India (e-mail: topksingh@gmail.com).
Rajendra Kumar is with Computer Science and engineering Department, Vidya College of Engineering, Meerut (Uttar Pradesh), India (phone: +91-9412002322, e-mail: rajendra04@gmail.com, website: http://www.rkronline.in).
Vijay Shankar Pandey is with the Board of Apprenticeship Training (SR), Chennai, India, (e-mail: vsp125@gmail.com).

Cite: P K Singh, Rajendra Kumar and Vijay Shankar Pandey, "An Efficient Algorithm for All Pair Shortest Paths," International Journal of Computer and Electrical Engineering vol. 2, no. 6, pp. 984-991, 2010.