| Peer-Reviewed

An Alternative Method of Floyd-Warshall Algorithm Is Proposed for Solving Shortest Path Problems Using Triangular Procedure

Received: 25 October 2022     Accepted: 18 November 2022     Published: 8 December 2022
Views:       Downloads:
Abstract

This paper presents a new approach for finding the shortest path compared with the Floyd-Warshall algorithm which is mostly used for determining the shortest path between every pair of nodes of network modeling problems. Finding the smallest route through a road network is one of the innumerable real-world applications of the shortest path problem. In this paper, we will discuss the existing Floyd-Warshall algorithm. Then we will explain our new approach to solving shortest-path problems. The method is developed based on a right-angle triangle. This technique of solving the shortest path problem brings out the same result as the existing Floyd-Warshall algorithm. Additionally, we demonstrate that the foundation of our algorithm is simpler to comprehend, which could be helpful for instructional reasons. An example verifies our algorithm and demonstrates how it is used. We hope this paper will give the reader an idea of the network modeling problems and their efficacy, enumerate the benefits gained, and identify areas for further improvement.

Published in Mathematics and Computer Science (Volume 7, Issue 6)
DOI 10.11648/j.mcs.20220706.12
Page(s) 113-117
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2022. Published by Science Publishing Group

Keywords

Network Programming, Shortest Path Problem, Floyd–Warshall Algorithm, Triangular Algorithm

References
[1] Paul A. Jensen, Operations Research Models and Methods, Wiley (1865).
[2] Gupta, P. K., D. S. Hira, Problem in Operation Research, S. Chand & Company Ltd, Ram Nagar.
[3] Introduction to Operation Research by prof. G. Srinivasan, IIT Madras.
[4] Operation Research: An introduction by Hamdy A. Taha, ninth edition 2011.
[5] R. E. Bellman, On a routing problem, Quarterly of Applied Mathematics 16 (1) (1958) 87–90.
[6] E. W. Dijkstra, A note on two problems in connection with graphs, Numeriskche Mathematik 1 (1959) 269–271.
[7] L. R. Ford, D. R. Fulkerson, Flows in Networks, Princeton University Press, Princeton, NJ, 1962.
[8] G. Gallo, S. Pallotino, Shortest paths algorithms, Annals of Operations Research 13 (1988) 3–79.
[9] B. V. Cherkassky, A. V. Goldberg, T. Radzik, Shortest paths algorithms: theory and experimental evaluation, Mathematical Programming 73 (2) (1996) 129–174.
[10] R. W. Floyd, Algorithm 97, Communications of the ACM 5–6 (1962) 345.
[11] S. Warshall, A theorem on boolean matrices, Journal of the ACM 9 (1962) 11–12Rn are yielded.
[12] Asghar Aini, Amir Salehipur, Speeding up Floyd-Warshall algorithm for the cycled shortest path Problems Shahid Sattari University, Iran.
[13] Hiller F. S., Liberman G. J., Introduction to Operations Research, The McGraw-Hill Companies, Inc., 2011.
[14] Prim and Floyd-Warshall Comparative Algorithms in Shortest Path Problem, Zuhri Ramadhan, Faculty of Science and Technology, Universitas Pembangunan Panca Budi, Medan, Indonesia, 2018.
[15] Improving The Floyd-Warshall All Pairs Shortest Paths Algorithm, Ismail H. Toroslu, Ankara, Terkey-2021.
Cite This Article
  • APA Style

    Md Zahidul Islam, Md Asadujjaman, Mahabub Rahman. (2022). An Alternative Method of Floyd-Warshall Algorithm Is Proposed for Solving Shortest Path Problems Using Triangular Procedure. Mathematics and Computer Science, 7(6), 113-117. https://doi.org/10.11648/j.mcs.20220706.12

    Copy | Download

    ACS Style

    Md Zahidul Islam; Md Asadujjaman; Mahabub Rahman. An Alternative Method of Floyd-Warshall Algorithm Is Proposed for Solving Shortest Path Problems Using Triangular Procedure. Math. Comput. Sci. 2022, 7(6), 113-117. doi: 10.11648/j.mcs.20220706.12

    Copy | Download

    AMA Style

    Md Zahidul Islam, Md Asadujjaman, Mahabub Rahman. An Alternative Method of Floyd-Warshall Algorithm Is Proposed for Solving Shortest Path Problems Using Triangular Procedure. Math Comput Sci. 2022;7(6):113-117. doi: 10.11648/j.mcs.20220706.12

    Copy | Download

  • @article{10.11648/j.mcs.20220706.12,
      author = {Md Zahidul Islam and Md Asadujjaman and Mahabub Rahman},
      title = {An Alternative Method of Floyd-Warshall Algorithm Is Proposed for Solving Shortest Path Problems Using Triangular Procedure},
      journal = {Mathematics and Computer Science},
      volume = {7},
      number = {6},
      pages = {113-117},
      doi = {10.11648/j.mcs.20220706.12},
      url = {https://doi.org/10.11648/j.mcs.20220706.12},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.mcs.20220706.12},
      abstract = {This paper presents a new approach for finding the shortest path compared with the Floyd-Warshall algorithm which is mostly used for determining the shortest path between every pair of nodes of network modeling problems. Finding the smallest route through a road network is one of the innumerable real-world applications of the shortest path problem. In this paper, we will discuss the existing Floyd-Warshall algorithm. Then we will explain our new approach to solving shortest-path problems. The method is developed based on a right-angle triangle. This technique of solving the shortest path problem brings out the same result as the existing Floyd-Warshall algorithm. Additionally, we demonstrate that the foundation of our algorithm is simpler to comprehend, which could be helpful for instructional reasons. An example verifies our algorithm and demonstrates how it is used. We hope this paper will give the reader an idea of the network modeling problems and their efficacy, enumerate the benefits gained, and identify areas for further improvement.},
     year = {2022}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - An Alternative Method of Floyd-Warshall Algorithm Is Proposed for Solving Shortest Path Problems Using Triangular Procedure
    AU  - Md Zahidul Islam
    AU  - Md Asadujjaman
    AU  - Mahabub Rahman
    Y1  - 2022/12/08
    PY  - 2022
    N1  - https://doi.org/10.11648/j.mcs.20220706.12
    DO  - 10.11648/j.mcs.20220706.12
    T2  - Mathematics and Computer Science
    JF  - Mathematics and Computer Science
    JO  - Mathematics and Computer Science
    SP  - 113
    EP  - 117
    PB  - Science Publishing Group
    SN  - 2575-6028
    UR  - https://doi.org/10.11648/j.mcs.20220706.12
    AB  - This paper presents a new approach for finding the shortest path compared with the Floyd-Warshall algorithm which is mostly used for determining the shortest path between every pair of nodes of network modeling problems. Finding the smallest route through a road network is one of the innumerable real-world applications of the shortest path problem. In this paper, we will discuss the existing Floyd-Warshall algorithm. Then we will explain our new approach to solving shortest-path problems. The method is developed based on a right-angle triangle. This technique of solving the shortest path problem brings out the same result as the existing Floyd-Warshall algorithm. Additionally, we demonstrate that the foundation of our algorithm is simpler to comprehend, which could be helpful for instructional reasons. An example verifies our algorithm and demonstrates how it is used. We hope this paper will give the reader an idea of the network modeling problems and their efficacy, enumerate the benefits gained, and identify areas for further improvement.
    VL  - 7
    IS  - 6
    ER  - 

    Copy | Download

Author Information
  • Department of Mathematics, University of Dhaka, Dhaka, Bangladesh

  • Department of Mathematics, University of Dhaka, Dhaka, Bangladesh

  • Department of Mathematics, University of Dhaka, Dhaka, Bangladesh

  • Sections