This study addresses a comparative analysis of shortest path algorithms based on graph theory. The shortest path problem plays a crucial role in various application fields, with Dijkstra's algorithm and the Bellman-Ford algorithm being representative algorithms for solving it. Dijkstra's algorithm performs optimally in graphs without negative weights and efficiently explores paths using a priority queue. In contrast, the Bellman-Ford algorithm has the advantage of being able to handle negative weights, but it has a relatively high time complexity. This paper compares the time and space complexities of the two algorithms and analyzes the suitable application cases for each. Through this analysis, the importance of selecting the appropriate algorithm for solving the shortest path problem is emphasized.

Keywords

Graph theory, Shortest path, Path algorithms, Dijkstra's algorithm and Bellman-Ford algorithm.