PathFinding Analyzer is a visualization tool which is focused on shortest path algorithms in Graph. The application has different algorithms which are designed for a 2D Grid, where the cost between the two consecutive cells is 1.
To run this application, use can click on this link to download the Executable JAR of the application.
Fig 1.0 Tutorial to the PathFinding Analyzer
-
Breadth -First Search (BFS)
BFS is a unweighted graph traversal algorithm that starts the traversal from the source node and explores all the neighbouring nodes. It follows the principle of level order traversal, where it selects the nearest node and explore all the unexplored nodes.
It is a great algorithm which is simple to implement using Queue. It also guarantees the shortest path from source to destination, if exists.
The Space Complexity of the BFS algorithm is b^d (branching factor raised to the depth of the graph).
Fig 1.1 Demo of the Breadth-First Search (BFS) Algorithm
-
Depth-First Search (DFS)
DFS is an algorithm for traversing or searching tree or graph data structures. THe algorithm starts at the source node and explores as far as possible along each branch before it bracktracks and follows the remaining edges of a node.
It is very inefficient algorithm for path-finding and it does not guarantee shortest path. It includes exhaustive searches of all the nodes by going ahead, if possible, else by backtracking. It uses Stack for its implementation. It can get stuck in an infinite loop, which is why it is not "Complete".
The Space Complexity of the DFS algorithm is O(log(d)) where is 'd' is the depth of the graph.
Fig 1.2 Demo of the Depth-First Search (DFS) Algorithm
-
A* Search
A* (pronounced as "A star") is a computer algorithm that is widely used in pathfinding and traversal. The algorithm efficiently plots a walkable path between multiple nodes, or points, on the graph. On a map with many obstacles, pathfinding from points AA to BB can be difficult. A robot, for instance, without getting much other direction, will continue until it encounters an obstacle, as in the path-finding example to the left below.
However, the A* algorithm introduces a heuristic into a regular graph-searching algorithm, essetially planning ahead at each step so a more optimal decision is made. With A*, a robot would instead find a path in a way similar to the diagram on the right below.
A* is an extension of Dijkstra's algorithm with some characteristics of Breadth-First Search (BFS).
To know more about the A* Algorithm, follow this link.
Fig 1.3 Demo of the A* Search Algorithm
-
Greedy Best-First Search
It is a suboptimal best-first search algorithm which works on the principle of A* Algorithm and always priorities the node with the lowest heuristic value without any consideration of the cost to get to that node. While this greedy GBFS algorithm can be effective in practice, it can be misled by an arbitrary amount if th heuristic is wrong. Hence, it does not gurantee shortest path.
To know more about the GBFS Algorithm, follow this link.
Fig 1.3 Demo of the Greedy Best-First Search (GBFS) Algorithm
Besides the Path-Finding Algorithms, the Maze Generation has been implemented using DFS Algorithm.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent