Graph Data Structure 6. The A* Pathfinding Algorithm

This is the sixth in a series of videos about the graph data structure. It includes a step by step walkthrough of the A* pathfinding algorithm (pronounced A Star) for a weighted, undirected graph. The A* pathfinding algorithm, and its numerous variations, is widely used in applications such as games programming, natural language processing, financial trading systems, town planning and even space exploration. This video demonstrates why the A* pathfinding algorithm may be more appropriate and more efficient than Dijkstra’s shortest path algorithm for many applications, because it is focussed on finding the shortest path between only two particular vertices. The video explains the need for an admissible heuristic, that is, a suitable estimate of the distance between each vertex in the graph and the destination vertex; the example shown here makes use of Manhattan distances for this purpose, calculated on the basis of the grid co-ordinates of each vertex. A description of the pseudocode that leads to an implemen