Volume 2 Number 6 (Dec. 2010)
Home > Archive > 2010 > Volume 2 Number 6 (Dec. 2010) >
IJCEE 2010 Vol.2 (6): 984-991 ISSN: 1793-8163
DOI: 10.7763/IJCEE.2010.V2.263

An Efficient Algorithm for All Pair Shortest Paths

P. K. Singh, Rajendra Kumar, and Vijay Shankar Pandey

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.

General Information

ISSN: 1793-8163
Frequency: Quarterly
Editor-in-Chief: Prof. Yucong Duan
Abstracting/ Indexing: EI (INSPEC, IET), Ulrich's Periodicals Directory, Google Scholar, EBSCO, ProQuest, and Electronic Journals Library
E-mail: ijcee@iap.org

What's New

  • Mar 20, 2019 News!

    IJCEE Vol. 11, No. 1 is available online now.   [Click]

  • Aug 06, 2018 News!

    IJCEE Vol. 8, No. 4 - Vol. 9, No. 1 have been indexed by EI (Inspec) Inspec, created by the Institution of Engineering and Tech.!   [Click]

  • Mar 20, 2019 News!

    The dois of published papers in Vol. 9, No. 1- Vol. 10, No. 4 have been validated by Crossref.

  • Dec 29, 2018 News!

    IJCEE Vol. 10, No. 4 is available online now.   [Click]

  • Oct 12, 2018 News!

    IJCEE Vol. 10, No. 3 is available online now.   [Click]

  • Read more>>