SkyRoute Planner: A Variant of Warshall's Algorithm

Team implementation of a C++ algorithm concerning a variant of a graph traversal problem given a maximum number of traversable edges.

📖 Context

This project was developed for the Laboratorio di Algoritmi examination of Prof. Marinella Sciortino, during the 2022/2023 Academic Year at the Università degli Studi di Palermo, Computer Science (L-31, 2086) course.

👥 Authors

Andrea Spinelli - Marco Valenti - Raffaele Terracino

🛠️ Technologies Used

• Languages: C++
• Frameworks/Libraries: CMake
• Other: Git

🚀 Installation and Startup

To compile and run this C++ project, you will need a C++ compiler and the make utility.

Note for Windows users: You can get g++ and make by installing a toolchain like MinGW-w64 or by using the Windows Subsystem for Linux (WSL). On macOS (with Xcode Command Line Tools) and Linux, these tools are typically pre-installed or easily available.

Instructions

1. Clone the Repository Open your terminal or command prompt and clone the repository.

   [git clone https://github.com/A-rgonaut/L-31-2023-Progetto-Lab-Algoritmi.git](https://github.com/A-rgonaut/L-31_SkyRoute_Planner_A_Variant_of_Warshall_s_Algorithm.git)
   cd L-31_SkyRoute_Planner_A_Variant_of_Warshall_s_Algorithm

2. Compile the Project Use the provided makefile to compile the source code. This will create an executable file in the main directory.

   make all

3. Run the Application You can now run the compiled program. The makefile includes a convenient command for this.

   make run

   Alternatively, you can run the executable directly:

   ./main

4. Interact with the Program Once running, the application will prompt you to enter the departure and arrival nodes (e.g., airport codes or numbers as defined in your dataset) in the console. It will then compute and display the shortest path.

✨ Key Features

This project is a C++ command-line application that finds the shortest path in a graph. It is designed to solve the flight route problem, using a custom-built graph data structure.

The core features of this implementation are:

1. C++ Implementation: The entire logic is written in C++ for high performance, which is ideal for algorithmic tasks. The code is well-structured into multiple files (graph.h, utilities.h) for better organization and reusability.

2. Custom Graph Data Structure: The project features a custom-built Graph class (defined in src/graph.h and src/graph.cpp) to represent the flight network, demonstrating a strong understanding of data structures from scratch.

3. File Parsing: It parses a custom dataset.txt file to dynamically build the graph in memory. This shows the ability to handle file I/O and custom data formats.

4. Shortest Path Algorithm: The program implements an efficient algorithm (likely Dijkstra's) to calculate the shortest path between two nodes (airports) specified by the user.

5. Command-Line Interface (CLI): The application is fully interactive via the command line. It prompts the user for input (departure and arrival airports) and prints the resulting optimal path directly to the console.