Comparative analysis of Prim and Dijkstra algorithms in shortest path problems

Abstract

Graph theory is a fundamental area of discrete mathematics concerned with modeling relationships between objects using vertices and edges. One of the most significant applications of graph theory is solving shortest path problems, which involve finding the minimum-cost route between two or more nodes in a network. Efficient algorithms for this purpose are essential in fields such as computer networks, transportation, and operations research. This research provides a comparative analysis of the Prim and Dijkstra algorithms, focusing on their application to the shortest path problem. While Prim's algorithm is primarily known for constructing Minimum Spanning Trees (MSTs), this study investigates its capability and efficiency in finding the shortest path between nodes in a graph. Dijkstra's algorithm, a standard for shortest path computations, is used as a comparative basis. The research highlights that while Dijkstra's algorithm is well-suited for finding the shortest path from a single source to all other nodes, Prim's algorithm, when adapted, can also yield optimal paths. A key part of this study is the examination of Mean Active Edges (MAE), which represents the average number of edges used during path construction, and Mean Cost (MC), which indicates the average total weight or cost of the paths found. The analysis also explores how both algorithms manage “active edges” during their execution. Prim’s algorithm uses a greedy approach, adding the smallest available edge that connects a new vertex to the growing tree, while avoiding cycles and ensuring connectivity. In contrast, Dijkstra’s algorithm expands paths by updating distances and maintaining a set of visited nodes to ensure the shortest routes are found. The study evaluates how the selection and management of these active edges impact the overall performance, speed, and accuracy of both algorithms in solving the shortest path problem, offering insights into their practical implications for real-world routing scenarios.