How does Dijkstra's Algorithm and A-Star compare?

Question

How is the Dijkstra algorithm differ from the A* algorithm as they seem to be similar to me? What are the pros and cons of Dijkstra’s algorithm and A* Algorithm?

Answer 1

Firstly, we will talk about Dijkstra’s algorithm:

The main advantage of Dijkstra’s is that it has an uninformed algorithm. This means it doesn’t need to know about the target node beforehand. And for this feature, it can be used where you do not have any prior knowledge of the graph and you can’t estimate the distance between each node and the target.

It comes in hand when you have multiple target nodes. Since Dijkstra picks edges with the smallest cost at each step it usually covers a large area of the graph. This is especially useful when you have multiple target nodes but you don't know which one is the closest.

Now comes the A* algorithm

If you ask what is the best 2-D path-finder algorithm then the answer is A* Algorithm.

It is a smart algorithm that separates it from the other conventional algorithms.

Here is the algorithm for the same:

// A* Search Algorithm

1.  Initialize the open list// open nodes

2.  Initialize the closed list// closed nodes

    put the starting node on the open 

    list (you can leave its f at zero)// f is the value which contains the addition of g and h

// g is the cost to move from the starting node

// h is the movement cost from a particular node to the destination node

3.  while the open list is not empty

    a) find the node with the least f on 

       the open list, call it "q"

    b) pop q off the open list

    c) generate q's 8 successors and set their 

       parents to q

    d) for each successor

        i) if successor is the goal, stop search

          successor.g = q.g + distance between successor and q

          successor.h = distance from goal to 

          successor (This can be done using many 

          ways, we will discuss three heuristics- 

          Manhattan, Diagonal and Euclidean 

          Heuristic)

          successor.f= successor.g + successor.h

        ii) if a node with the same position as 

            successor is in the OPEN list which has a 

           lower f than successor, skip this successor

        iii) if a node with the same position as 

            successor  is in the CLOSED list which has

            a lower f than successor, skip this             successor otherwise, add the node to the open list

     end (for loop)

    e) push q on the closed list

    end (while loop)

People choose A* over Dijkstra’s algorithm as Dijkstra’s algorithm fails on the negative edge weights. For example, if we take three nodes named A, B, C and forming an undirected graph with edges AB=3, AC=4, BC=-2, then the path from A to C costs 1 and from A to B it costs 2. Now if we apply Dijkstra's algorithm, from A, it will examine B because it is the closest node and it will assign the cost of 3 to it and mark the node close that means the updated cost will never be reevaluated. Thus, it cannot evaluate negative edge weights.

While in other cases people choose Dijkstra’s algorithm over A* because  A* algorithm cannot be applied to those graphs which have many target nodes. If you have many target nodes and you don't know which one is closest to the main one, A* is not very optimal. This is because it needs to be run several times (once per target node) in order to get to all of them.