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.