Welcome to myPath!
What are pathfinding algorithms?
Pathfinding algorithms are a class of algorithms that find the shortest path from one node to another on a given graph.
What is Path Visualizer?
It is a visualizing tool that shows how different pathfinding algorithms work.
The program's objective is to go from the start node to the end node using a pathfinding algorithm. The program can only move horizontally or vertically, with each movement having a cost of one. Once the program is complete, the shortest path will be illuminated in yellow.
Step 1: Choose An Algorithm
Click the 'Algorithms' tab and select one of the algorithms from the dropdown menu.
If you want to learn more about the algorithms listed, then click the 'Info' button that is located at the bottom of the page.
Step 2: Draw Walls
Click or hold your mouse down over cells to create walls.
Step 3: Press Start
Press the Start button in the upper right-hand corner to start your pathfinding algorithm!
Optional: Move Start/End
Hold the mouse down and drag the start/end node to a new location.
Optional: Mazes
Click the 'Mazes' tab and select one of the algorithms from the dropdown menu and a randomized maze will be created for you.
Enjoy Path Visualizer!
If you want to revisit this tutorial, click the 'Tutorial' button at the end of the page.
If you want to see other projects that I've created, check out my github!
GithubAlgorithms
How It Works: DFS starts at the root node and explores as far as possible along each branch before backtracking.
Analysis: This is a poor algorithm for pathfinding. It is unweighted and does not guarantee the shortest path.
Fun Fact: This algorithm was first investigated in the 19th century by French Mathematician Charles Trémaux.
How It Works: BFS starts at the root node and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Analysis: This is an OK algorithm for pathfinding. It is unweighted but guarantees the shortest path.
Fun Fact: This algorithm was first invented in 1945 by Konrad Zuse and was submitted in his rejected PhD thesis, but was not published until 1972.
How It Works: In Dijkstra's algorithm, all of the nodes in the graph (except the starting node) are initialized with a distance equal to 'infinity.' These distances represents the cost to get from the starting node to the current node, with the starting node having a distance of zero. At the beginning of each iteration, the node with the smallest distance that hasn't been explored yet is visited. These nodes are stored in a min-heap data structure. When a node is visited, all of the neighbors' distances are updated, and if any of the neighbor's distances are lessened, then the algorithm pushes the node onto the min-heap. This continues until the end node has been reached.
Analysis: This is an OK algorithm for pathfinding. This algorithm performs very well in trees with unequal distances between nodes. But since this program only explores horizontally/vertically (with each move costing one), it behaves exactly the same as BFS. It is unweighted but guarantees the shortest path.
Fun Fact: Edsger Dijkstra invented this algorithm in twenty minutes.