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.
