Heuristic for A* algorithm

Hi

I was reading into the A* algorithm. One of the key elements of the algorithm is that it uses a heuristic to approximate the distance to the target.

As I understand it, the heuristic function can vary but it is common to use something like a "Manhattan distance" or "Euclidean distance" which is something like moving through blocks on a chessboard.

What I don't understand is how you can calculate a heuristic function for a graph. I understand how you can do this for something like a grid where you can calculate the horizontal and vertical difference but you can't do this for a vertex (because a graph doesn't have this rigid structure).

I note that the Wiki on shortest path (https://en.wikipedia.org/wiki/Shortest_path_problem) doesn't really refer to A* for graphs.

What am I missing here?

Thanks
If each node in the graph has an x and y coordinate then you could use those to calculate the euclidean distance to the goal.

But if you don't have any such information that allows you to come up with a meaningful heuristic function then A* is not going to help and you probably should use Dijkstra's algorithm instead.
Last edited on
Topic archived. No new replies allowed.