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 |
Network Programming, Shortest Path Problem, Floyd–Warshall Algorithm, Triangular Algorithm
| [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. |
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
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
Share This Article
Twitter
Linked In
Facebook
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}
}
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 -
Information
Email: