Pathfinding is the plotting of the shortest route between two points. Pathfinding method searches a graph by starting at one vertext and exploring adjacent nodes until the destination node is reached, generally with the intent of finding the shortest route.
Two primary problems of pathfinding are to find a path between two nodes in a graph and to find the optimal shortest path. Although there exists algorithms such as Breadth-first and depth-first search to address the first problem but they run in linear time O(V+E) to traverse an entire graph; where v is the number of vertices and E is the number of edges between vertices.To address the latter issue which is finding the optimal shortest path, Dijkstra and A* algorithm are considered as the best algorithms on the graph theory.
This algorithm begins with a start node and an "open set" of candidate nodes. At each step, the node in the open set with the lowest distance from the start is examined. The node is marked "closed", and all nodes adjacent to it are added to the open set if they have not already been examined.This process repeats until a path to the destination has been found. Since the lowest distance nodes are examined first, the first time the destination is found,the path to it will be the shortest path
Wikipedia click here to read more
