Dijkstra and A* Algorithms: Why is A* faster?

Question

I am learning about Dijkstra's Algorithm and the A* Algorithm and I have manually worked through the graph attached here, which is supposed (I think) to demonstrate that the A* Algorithm is faster than the Dijkstra one. The sequence in which I chose the nodes is indicated by the circled numbers. I can see that the process is fairly simple but there are plenty of possibilities for human error, so please bear with me.

My course book says that the A* will be quicker.

I can't see why this is true. Have I worked through the graph incorrectly?

It seems to me that both methods require that all nodes must be visited so where is the increase in efficiency?

I have read what I can on Stack Overflow about this so please don't point me at earlier posts unless there is a very good reason.

Answer 1

I absolutely don't understand the attached images and what you try to do on it. What I can say is that Dijkstra an A* algorithm are pathfinding methods:

Dijkstra algorithm is an exploration method that let you find the shortest path to any vertex of the graph. The idea is to always consider the vertices that you reach from the cheapest (closest) node of the queue.

You may run this algorithm to find the shortest path from a specific node $s$ to a specific node $t$. But you can also use it to determine global properties of the distances from $s$. Or for instance, build a tree that let you backtrack the path from $s$ to any vertex.

A* algorithm is basically a Dijkstra method that use an additional heuristic to sort the nodes of the queue. On distance problem, this heuristic is generally based on the euclidian distance from the node to the aim. It favorises the exploration of the nodes that are more likely to go in the good direction. So this specialization of Dijkstra algorithm is only used to go from a specific node $s$ to a specific node $t$. It is generally largely faster but does not guarantee to find the optimal path (in the ver).

I suggest you play with this pathfinding simulation tool

Answer 2

Yes, I find it difficult to explain my problem. After some reflection I think I must be doing the A* process incorrectly. I'm guessing that the node queue (as you call it) must be determined by the least sum of (distance to adjacent node + heuristic ). Maybe that's where I have got it wrong.

Actually Wikipedia states:

At each iteration of its main loop, A* needs to determine which of its paths to extend. It does so based on the cost of the path and an estimate of the cost required to extend the path all the way to the goal. Specifically, A* selects the path that minimizes

f ( n ) = g ( n ) + h ( n )

where n is the next node on the path, g(n) is the cost of the path from the start node to n, and h(n) is a heuristic function that estimates the cost of the cheapest path from n to the goal. A* terminates when the path it chooses to extend is a path from start to goal or if there are no paths eligible to be extended. The heuristic function is problem-specific. If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, A* is guaranteed to return a least-cost path from start to goal.

So I think I've answered my own question.