The graph data is based on the London subway network which is openly available and can be found here. I used this data rather than generating some random points on a grid to give a more realistic feel to the applications of graph algorithms. This was inspired by one of my course projects based on implementing and evaluating the KPIs on graph algorithms - as a visual learner, I wanted to build a visualizer to actually see how the stations and lines are positioned, and how the algorithms traverses through them.
There's many other pathfinding visualizers out there but this is one that I created to help strengthen my knowledge of graph algorithms. The goal was not to make a stunning UI, but to have a working interface that does its job of observing how these algorithms perform step by step. I chose to use Python's Tkinter library so that the application stays minimalistic while displaying the necessary graph details and pathfinding inputs/settings.
- Clone the repo
git clone [email protected]:angelaw7/pathfinding-visualizer.git
- Go to project directory
cd pathfinding-visualizer
- Run the project; this will open the GUI
py main.py
- Dijkstra's Algorithm
Dijkstra's algorithm is used to find the shortest path between two subway stations / nodes. The shortest path is determined by the minimal amount of time to travel between the source and destination stations.
dijkstras.mp4
- A* Algorithm
The A-Star algorithm runs similarly to Dijkstra's but also uses a heuristic to guide which node to visit next. The heuristic used for this project was the euclidean distance between two stations, based on their geographical coordinates, as we would expect that choosing the path that gets us closer to the destination station is usually a good idea.
astar.mp4
- Breadth First Search
Breadth first search's strengths lie in determining the path with the least connections, rather than the shortest path based on time. This could potentially help to avoid switching lines as a tradeoff for a slightly longer ride.
bfs.mp4
- Travelling Salesman Problem (subset of nodes to cover)
This is personally my favourite, although it does lag a bit while running the visualization since it needs to make quite a bit of calculations. The goal of this algorithm is to find the most optimal path to cover all the stations specified in the least amount of time, while returning to the first station in the end. For this problem, it was important to use dynamic programming rather than a brute-force permutations approach to reduce the amount of repetitive computation needed. It uses Dijkstra's to find the path between two stations, although A* could have also been used.
tsp.mp4
- Highlight a specific subway line
- Select the speed of which to run the visualization
- Show/hide the breakdown of the subway lines in the path found