A Review of Shortest Path Problem in Graph Theory

Abstract

A graph's shortest-path algorithm identifies the route with the lowest cost connecting two vertices. The literature covers a wide range of shortest-path algorithms and is interdisciplinary. The survey of shortest-path algorithms in this paper is based on a taxonomy that is presented in the paper. The varieties of the shortest-path issue comprise one dimension of this taxonomy. Due to each solution's space and temporal challenges, no general algorithm can solve all incarnations of the shortest-path problem. The shortest-path algorithm's ability to operate on a static or dynamic graph, its ability to provide accurate or approximative results, and whether or not it aims to attain timedependence rather than just goal-directedness are all significant aspects of the taxonomy. According to the proposed taxonomy, shortest-path algorithms are examined and categorized in this survey. The poll also outlines the issues and suggested fixes related to each taxonomy category.