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 (Print)
Abbreviated Title: Int. J. Comput. Electr. Eng.
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

  • Jun 03, 2019 News!

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

  • Aug 20, 2019 News!

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

  • Jun 03, 2019 News!

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

  • Mar 20, 2019 News!

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

  • Mar 20, 2019 News!

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

  • Read more>>