Introduction to Graph Theory: Finding The Shortest Path (Part 2)

February 25, 2013 in Uncategorized by Adrian Marius

A couple of weeks ago I did anĀ introduction to graph theory using Dijkstra’s algorithm. I received some awesome feedback so this week I want to take it a step further and build on that using the A* algorithm. The big difference between A* and Dijkstra’s algorithm is the addition of a heuristic function. This heuristic function allows us to give a best guess of which path to take rather than always taking the path that is the shortest distance from the source node. If you’re a gamer or someone looking to get into game development this algorithm is the basis of how path finding is done in a lot of games.

 

Read the full article