Finding the shortest path in a simple connected graph is an important problem in graph theory and computer science with numerous applications, such as navigation, networks, and path optimization. This thesis presents various strategies for finding the shortest path, ranging from intuitive methods, such as a local greedy method and an exhaustive search of all paths, to specialized algorithms, such as Dijkstra’s algorithm and A*. It discusses the data structures used by these algorithms for efficient operation and evaluates their correctness and performance. Each method is demonstrated on a fixed example graph.
|
