A mini-game that implements A*, Dijkstra, BFS and Bellman Ford algorithms.
-
A* is an informed search algorithm that finds the shortest path between two points by making a lowest-cost path tree from the start node to the target node. It uses a function f(n) that estimates the total cost of a path using that node and is based on heuristic methods to achieve optimality.
-
Dijkstra’s algorithm is a graph search algorithm that finds the shortest path between two points in a graph. It works by assigning tentative distances to all nodes and then iteratively selecting the node with the smallest tentative distance and updating its neighbors’ tentative distances until the target node is reached.
-
Breadth-first search (BFS) is a graph search algorithm that explores all the vertices of a graph in breadth-first order. It starts at the tree root and explores all the neighboring nodes at the present depth level before moving on to the nodes at the next depth level.
-
Bellman-Ford algorithm is a graph search algorithm that computes the shortest paths from a single source vertex to all other vertices in a weighted graph. It can handle graphs with negative edge weights and can detect negative cycles.
- The first click of the left mouse button marks the starting point.
- The second click of the left mouse button marks the ending point.
- The rest of the clicks mean the construction of the wall.
- By clicking the right mouse button we can erase the selected area.
- The 1 key on the keyboard represents the A* algorithm.
- The 2 key on the keyboard represents the Dijksrta algorithm.
- The 3 key on the keyboard represents the BFS algorithm.
- The 4 key on the keyboard represents the Bellman Ford algorithm.
- The space key resets the fields.
Python 3.10 and later. Pygame
- Download file main.py
- Open cmd
- Go to the folder where main.py is located
- Use command "python main.py"
This project is licensed under the MIT License.