This project is part of the second practical assignment for the Data Structures (ED) course. The objective of this work is to apply data structures and algorithms to solve a graph traversal problem. The problem we aim to solve can be summarized as follows:
“Linque, a legendary hero, is lost in the Fog Forest, which is becoming increasingly dense and magical. He must escape quickly before the fog traps him forever. The forest contains n clearings and m one-way trails, some of which have portals that do not consume energy. Linque is exhausted and has s units of energy, allowing him to use the portals at most k times. Starting at clearing 0, he needs to reach clearing n-1 without exceeding the limits of energy and portals. The goal is to determine whether Linque can escape the forest under these constraints.”
To solve this problem, we will utilize graph traversal algorithms, specifically Dijkstra's algorithm and the A (A-star) algorithm*. However, for the implementation of these algorithms, the use of various data structures is essential. These include structures to model the forest as a graph, and a priority queue for the traversal algorithms, among others.
As the focus of this course is on data structures, we will emphasize how these structures are implemented, how their design impacts the problem's solution, and in which contexts each type of structure is more suitable. We will also analyze their effects on the performance and efficiency of the solution.
Additionally, we will perform complexity analysis and experimental tests to evaluate the algorithms and data structures under different scenarios.