The shortest route technique is a fundamental problem in various fields, including transportation, logistics, network routing, and robotics. In this paper, we have discussed a prominent algorithm, namely Dijkstra's algorithm, and propose an alternative method for addressing these problems. A thorough comparison is conducted between the proposed algorithm and Dijkstra's algorithm, considering factors such as solution accuracy and computational efficiency. The experimental results indicate that our proposed method yields identical results to the existing method but with significantly reduced computation time. By leveraging advancements in computational power and algorithmic design, our proposed technique addresses the limitations of existing methods and offers new avenues for optimizing route planning processes. We begin by reviewing the classical algorithms commonly used for solving the shortest route problem, such as Dijkstra's algorithm. While this algorithm has proven its effectiveness over the years, it faces challenges when applied to large-scale networks and real-time applications due to its computational complexity. Our approach incorporates advanced data structures and optimization strategies to efficiently handle massive network graphs. Additionally, we integrate machine learning models to learn from historical data, allowing for the prediction of traffic patterns and considering dynamic factors in route planning.
| Published in | American Journal of Science, Engineering and Technology (Volume 8, Issue 3) |
| DOI | 10.11648/j.ajset.20230803.14 |
| Page(s) | 146-151 |
| 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), 2023. Published by Science Publishing Group |
Network Routing, Dijkstra's Algorithm, Floyd's Algorithm, Triple Operation, Vehicle Routing Problem
| [1] | Taha H. A., Operations Research An Introduction, Prentice Hall of India Pvt. Ltd, New Delhi, 1999. |
| [2] | Winston, W. L., J. B. Goldberg, 2004, “Operations Research: Applications and Algorithms”, Thomson Brooks. |
| [3] | https://mathinsight.org/network_introduction. |
| [4] | https://www.chegg.com/homework-help/questions-and-answers/d-10-10-use-dijkstra-s-algorithm-findlength-shortest-path-vertices-z-following-weighted-g-q69930813 |
| [5] | https://studylib.net/doc/18121752/lecture-18-solving-shortest-path-problem--dijkstra-s-algo... |
| [6] | https://www.uobabylon.edu.iq/eprints/publication_4_9401_1410.pdf |
| [7] | https://www.ques10.com/p/41050/single-source-shortest-path-1 |
| [8] | http://mdcollege.in/wp-content/uploads/2019/08/djikstras-algorithm.pdf |
| [9] | https://medium.com/@letslearnsomething95/dijkstras-shortest-path-finding-algorithm-with-a-solvedexample-df892915b0ca |
| [10] | https://www.coursehero.com/file/p67feerr/Distance-Value-Update-and-Current-Node-Designation-Update-Let-i-be-the-index-of |
| [11] | Aardal, K. I., van der Veen, J. A., & Weismantel, R. (2018). The Traveling Salesman Problem. In 50 Years of Integer Programming 1958-2008 (pp. 53-84). Springer. |
| [12] | B. Korte and J. Vygen, “Network Flows,” pp. 153–184, 2000, doi: 10.1007/978-3-662-21708-5_8. |
| [13] | R. Danchick, “An Exact Ranked Linear Assignments Solution to the Symmetric Traveling Salesman Problem,” OAlib, vol. 07, no. 03, pp. 1–8, 2020, doi: 10.4236/OALIB.1106159. |
| [14] | Z. Sun et al., “Optimal Path Finding Method Study Based on Stochastic Travel Time,” J Transp Technol, vol. 3, no. 4, pp. 260–265, Oct. 2013, doi: 10.4236/JTTS.2013.34027. |
APA Style
Md. Mehedi Hassan, Md. Asadujjaman, Md. Golam Robbani. (2023). A Modified Approach of Dijkstra’s Method for Finding Shortest Path in a Weighted Directed Graph. American Journal of Science, Engineering and Technology, 8(3), 146-151. https://doi.org/10.11648/j.ajset.20230803.14
ACS Style
Md. Mehedi Hassan; Md. Asadujjaman; Md. Golam Robbani. A Modified Approach of Dijkstra’s Method for Finding Shortest Path in a Weighted Directed Graph. Am. J. Sci. Eng. Technol. 2023, 8(3), 146-151. doi: 10.11648/j.ajset.20230803.14
AMA Style
Md. Mehedi Hassan, Md. Asadujjaman, Md. Golam Robbani. A Modified Approach of Dijkstra’s Method for Finding Shortest Path in a Weighted Directed Graph. Am J Sci Eng Technol. 2023;8(3):146-151. doi: 10.11648/j.ajset.20230803.14
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.ajset.20230803.14,
author = {Md. Mehedi Hassan and Md. Asadujjaman and Md. Golam Robbani},
title = {A Modified Approach of Dijkstra’s Method for Finding Shortest Path in a Weighted Directed Graph},
journal = {American Journal of Science, Engineering and Technology},
volume = {8},
number = {3},
pages = {146-151},
doi = {10.11648/j.ajset.20230803.14},
url = {https://doi.org/10.11648/j.ajset.20230803.14},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajset.20230803.14},
abstract = {The shortest route technique is a fundamental problem in various fields, including transportation, logistics, network routing, and robotics. In this paper, we have discussed a prominent algorithm, namely Dijkstra's algorithm, and propose an alternative method for addressing these problems. A thorough comparison is conducted between the proposed algorithm and Dijkstra's algorithm, considering factors such as solution accuracy and computational efficiency. The experimental results indicate that our proposed method yields identical results to the existing method but with significantly reduced computation time. By leveraging advancements in computational power and algorithmic design, our proposed technique addresses the limitations of existing methods and offers new avenues for optimizing route planning processes. We begin by reviewing the classical algorithms commonly used for solving the shortest route problem, such as Dijkstra's algorithm. While this algorithm has proven its effectiveness over the years, it faces challenges when applied to large-scale networks and real-time applications due to its computational complexity. Our approach incorporates advanced data structures and optimization strategies to efficiently handle massive network graphs. Additionally, we integrate machine learning models to learn from historical data, allowing for the prediction of traffic patterns and considering dynamic factors in route planning.},
year = {2023}
}
TY - JOUR T1 - A Modified Approach of Dijkstra’s Method for Finding Shortest Path in a Weighted Directed Graph AU - Md. Mehedi Hassan AU - Md. Asadujjaman AU - Md. Golam Robbani Y1 - 2023/07/31 PY - 2023 N1 - https://doi.org/10.11648/j.ajset.20230803.14 DO - 10.11648/j.ajset.20230803.14 T2 - American Journal of Science, Engineering and Technology JF - American Journal of Science, Engineering and Technology JO - American Journal of Science, Engineering and Technology SP - 146 EP - 151 PB - Science Publishing Group SN - 2578-8353 UR - https://doi.org/10.11648/j.ajset.20230803.14 AB - The shortest route technique is a fundamental problem in various fields, including transportation, logistics, network routing, and robotics. In this paper, we have discussed a prominent algorithm, namely Dijkstra's algorithm, and propose an alternative method for addressing these problems. A thorough comparison is conducted between the proposed algorithm and Dijkstra's algorithm, considering factors such as solution accuracy and computational efficiency. The experimental results indicate that our proposed method yields identical results to the existing method but with significantly reduced computation time. By leveraging advancements in computational power and algorithmic design, our proposed technique addresses the limitations of existing methods and offers new avenues for optimizing route planning processes. We begin by reviewing the classical algorithms commonly used for solving the shortest route problem, such as Dijkstra's algorithm. While this algorithm has proven its effectiveness over the years, it faces challenges when applied to large-scale networks and real-time applications due to its computational complexity. Our approach incorporates advanced data structures and optimization strategies to efficiently handle massive network graphs. Additionally, we integrate machine learning models to learn from historical data, allowing for the prediction of traffic patterns and considering dynamic factors in route planning. VL - 8 IS - 3 ER -
Information
Email: