This project aims to analyze and compare the performance of different algorithms for solving the shortest path problem. Shortest path problems arise in various real-world scenarios such as navigation systems, logistics, and network routing. The goal of this project is to determine the most efficient algorithm for finding the shortest path in different graph types and scenarios.
Shortest path algorithms play a crucial role in optimizing resource usage and providing fast and accurate solutions in various applications. By comparing the performance of algorithms like Dijkstra, Bellman-Ford, Floyd-Warshall, and A*, this project seeks to identify the algorithm that offers the best performance across different graph structures and characteristics. The scope of the project includes:
- Creating graphs with various characteristics (e.g., low density, high density, negative weights)
- Implementing different shortest path algorithms in Python
- Measuring the execution time of each algorithm
- Evaluating the results and determining the most suitable algorithm for different scenarios
- Simulating real-world scenarios to showcase the behavior of the algorithms in practical applications
-
Graph Generation: Different types of graphs will be generated to represent various scenarios. These graphs will include nodes, edges, and different weights.
-
Algorithm Implementation: Dijkstra, Bellman-Ford, Floyd-Warshall, and A* algorithms will be implemented in Python. Each algorithm will be implemented as a separate function and tested extensively.
-
Performance Measurement: Execution time of each algorithm will be measured using time stamps. The time stamps will be taken before and after running the algorithms, and the difference will indicate the execution time.
-
Result Evaluation: The results will be evaluated based on different graph types and characteristics. The performance of each algorithm will be compared, and the most efficient one will be determined.
-
Simulation of Real-World Scenarios: Various simulations will be conducted to demonstrate how the algorithms perform in real-world scenarios such as navigation systems and network routing.
Users can access different shortest path problem files by selecting different branches:
- Dijkstra: Contains files related to the Dijkstra algorithm implementation.
- Bellman-Ford: Contains files related to the Bellman-Ford algorithm implementation.
- Floyd-Warshall: Contains files related to the Floyd-Warshall algorithm implementation.
- Astar: Contains files related to the A* algorithm implementation.
- Ebrar ATABAY: Project Lead
Feel free to contribute to the project by forking the repository and creating pull requests.