| Peer-Reviewed

A Modified Approach of Dijkstra’s Method for Finding Shortest Path in a Weighted Directed Graph

Received: 8 June 2023     Accepted: 25 June 2023     Published: 31 July 2023
Views:       Downloads:
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.

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

Keywords

Network Routing, Dijkstra's Algorithm, Floyd's Algorithm, Triple Operation, Vehicle Routing Problem

References
[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.
Cite This Article
  • 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

    Copy | Download

    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

    Copy | Download

    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

    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}
    }
    

    Copy | Download

  • 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  - 

    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