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.

How It Works: GBFS tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. It evaluates nodes on a heuristic function, which in myPath is the Euclidean distance from the current node to the end node.

Analysis: This is a poor algorithm for pathfinding. It is weighted but does not guarantee the shortest path.

How It Works: A* uses the same min-heap data structure that is implimented in Dijkstra's, but it expands upon Dijkstra's criteria for selecting the next node to explore. Dijkstra's chooses the node with the smallest distance from the starting node to be explored next. However, A* ranks nodes differently: it has a heuristic function that evaluates how far a node has traveled from the starting node and how far it is from the end node. This heuristic function makes the algorithm 'smart' since it is able to expand in a direction of interest. My implimentation of A* uses Euclidean distance for the end node distance calculation.

Analysis: This is the one of the best algorithms for pathfinding. It is weighted and it guarantees the shortest path.

Fun Fact: A* was first created for the 'Shakey Project', which had the aim of building a mobile robot that could plan its own actions. It was later published in 1968 by Stanford Research Institute scientists.

How It Works: It gives shortest possible route that visits every city/Node exactly once Given a set of Nodes and distance between every pair of Node

Analysis: This is a good algorithm for pathfinding if there are more than one ending node. It is weighted and it guarantees the shortest path.

How It Works: Jump Point Search is an optimization of A* for uniform cost grids. It reduces symmertries in the search procedure by graph pruning, which eliminates certain nodes to explore based on the assumptions that can be made about the current node's neighbors (as long as certain conditions are satisfied). My implimentation only considers straight horizontal and vertical 'jumps.' In the original JPS paper, it also considers diagonal jumps, but since my program only moves horizontally and vertically, I decided to not impliment diagonal jumps. This made the algorithm non-optimal, sometimes resulting in the algorithm not being able to find the end node. Despite this, I decided to leave this algorithm in myPath to demonstrate the different types of algorithms out there.

Analysis: This is a great algorithm for pathfinding when there is an explicit maze drawn. It is weighted, but it does not guarantee the shortest path.

Fun Fact: JPS was first published in 2011, which is more than 40 years after A* was first published.