179

I was looking at what the guys in the Mario AI Competition have been doing and some of them have built some pretty neat Mario bots utilizing the A* (A-Star) Pathing Algorithm.

alt text
(Video of Mario A* Bot In Action)

My question is, how does A-Star compare with Dijkstra? Looking over them, they seem similar.

Why would someone use one over the other? Especially in the context of pathing in games?

3

12 Answers 12

209

Dijkstra is a special case for A* (when the heuristics is zero).

7
  • 1
    In dijkstra, we only consider the distance from the source right? And the minimum vertex is taken into consideration?
    – Kraken
    Apr 26, 2013 at 22:18
  • 5
    I thought A* is a special case for Dijkstra where they use a heuristic. Since Dijkstra was there first afaik.
    – Madmenyo
    Aug 23, 2013 at 17:36
  • 56
    @MennoGouw: Yes Dijkstra's algorithm was developed first; but it is a special case of the more general algorithm A*. It is not at all unusual (in fact, probably the norm) for special cases to be discovered first, and then subsequently be generalized . Sep 2, 2013 at 15:37
  • 2
    A* and the use of heuristics are discussed well in Norvig and Russel's AI book Oct 3, 2016 at 18:44
  • 1
    Does this mean that Djikstra and Uniform Cost Search is the same thing?
    – Erro
    Dec 8, 2016 at 21:27
134

Dijkstra:

It has one cost function, which is real cost value from source to each node: f(x)=g(x).
It finds the shortest path from source to every other node by considering only real cost.

A* search:

It has two cost function.

  1. g(x): same as Dijkstra. The real cost to reach a node x.
  2. h(x): approximate cost from node x to goal node. It is a heuristic function. This heuristic function should never overestimate the cost. That means, the real cost to reach goal node from node x should be greater than or equal h(x). It is called admissible heuristic.

The total cost of each node is calculated by f(x)=g(x)+h(x)

A* search only expands a node if it seems promising. It only focuses to reach the goal node from the current node, not to reach every other nodes. It is optimal, if the heuristic function is admissible.

So if your heuristic function is good to approximate the future cost, than you will need to explore a lot less nodes than Dijkstra.

22

What previous poster said, plus because Dijkstra has no heuristic and at each step picks edges with smallest cost it tends to "cover" more of your graph. Because of that Dijkstra could be more useful than A*. Good example is when you have several candidate target nodes, but you don't know, which one is closest (in A* case you would have to run it multiple times: once for each candidate node).

1
  • 20
    If there are several potential goal nodes, one could simply change the goal testing function to include them all. This way, A* would only need to be run once. Apr 4, 2010 at 2:11
9

Dijkstra's algorithm would never be used for pathfinding. Using A* is a no-brainer if you can come up with a decent heuristic (usually easy for games, especially in 2D worlds). Depending on the search space, Iterative Deepening A* is sometimes preferable because it uses less memory.

3
  • 6
    Why would Dijkstra's never be used for pathfinding? Can you elaborate?
    – KingNestor
    Aug 26, 2009 at 5:47
  • 2
    Because even if you can come up with a lousy heuristic, you'll do better than Dijkstra. Sometimes even if it's inadmissible. It depends on the domain. Dijkstra also won't work in low-memory situations, whereas IDA* will. Aug 26, 2009 at 5:59
  • I found the slides here: webdocs.cs.ualberta.ca/~jonathan/PREVIOUS/Courses/657/Notes/… Dec 16, 2012 at 0:23
8

Dijkstra is a special case for A*.

Dijkstra finds the minimum costs from the starting node to all others. A* finds the minimum cost from the start node to the goal node.

Dijkstra's algorithm would never be used for path finding. Using A* one can come up with a decent heuristic. Depending on the search space, iterative A* is is preferable because it uses less memory.

The code for Dijkstra's algorithm is:

// A C / C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph

#include <stdio.h>
#include <limits.h>

// Number of vertices in the graph
#define V 9

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
 // Initialize min value
 int min = INT_MAX, min_index;

  for (int v = 0; v < V; v++)
   if (sptSet[v] == false && dist[v] <= min)
     min = dist[v], min_index = v;

   return min_index;
}

 int printSolution(int dist[], int n)
 {
  printf("Vertex   Distance from Source\n");
  for (int i = 0; i < V; i++)
     printf("%d \t\t %d\n", i, dist[i]);
  }

void dijkstra(int graph[V][V], int src)
{
 int dist[V];     // The output array.  dist[i] will hold the shortest
                  // distance from src to i

 bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest
                 // path tree or shortest distance from src to i is finalized

 // Initialize all distances as INFINITE and stpSet[] as false
 for (int i = 0; i < V; i++)
    dist[i] = INT_MAX, sptSet[i] = false;

 // Distance of source vertex from itself is always 0
 dist[src] = 0;

 // Find shortest path for all vertices
 for (int count = 0; count < V-1; count++)
 {
   // Pick the minimum distance vertex from the set of vertices not
   // yet processed. u is always equal to src in first iteration.
   int u = minDistance(dist, sptSet);

   // Mark the picked vertex as processed
   sptSet[u] = true;

   // Update dist value of the adjacent vertices of the picked vertex.
   for (int v = 0; v < V; v++)

     // Update dist[v] only if is not in sptSet, there is an edge from 
     // u to v, and total weight of path from src to  v through u is 
     // smaller than current value of dist[v]
     if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
                                   && dist[u]+graph[u][v] < dist[v])
        dist[v] = dist[u] + graph[u][v];
 }

 // print the constructed distance array
 printSolution(dist, V);
 }

// driver program to test above function
int main()
 {
 /* Let us create the example graph discussed above */
 int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                  {4, 0, 8, 0, 0, 0, 0, 11, 0},
                  {0, 8, 0, 7, 0, 4, 0, 0, 2},
                  {0, 0, 7, 0, 9, 14, 0, 0, 0},
                  {0, 0, 0, 9, 0, 10, 0, 0, 0},
                  {0, 0, 4, 14, 10, 0, 2, 0, 0},
                  {0, 0, 0, 0, 0, 2, 0, 1, 6},
                  {8, 11, 0, 0, 0, 0, 1, 0, 7},
                  {0, 0, 2, 0, 0, 0, 6, 7, 0}
                 };

dijkstra(graph, 0);

return 0;
}

The code for A* algorithm is:

class Node:
def __init__(self,value,point):
    self.value = value
    self.point = point
    self.parent = None
    self.H = 0
    self.G = 0
def move_cost(self,other):
    return 0 if self.value == '.' else 1

def children(point,grid):
x,y = point.point
links = [grid[d[0]][d[1]] for d in [(x-1, y),(x,y - 1),(x,y + 1),(x+1,y)]]
return [link for link in links if link.value != '%']
def manhattan(point,point2):
return abs(point.point[0] - point2.point[0]) + abs(point.point[1]-point2.point[0])
def aStar(start, goal, grid):
#The open and closed sets
openset = set()
closedset = set()
#Current point is the starting point
current = start
#Add the starting point to the open set
openset.add(current)
#While the open set is not empty
while openset:
    #Find the item in the open set with the lowest G + H score
    current = min(openset, key=lambda o:o.G + o.H)
    #If it is the item we want, retrace the path and return it
    if current == goal:
        path = []
        while current.parent:
            path.append(current)
            current = current.parent
        path.append(current)
        return path[::-1]
    #Remove the item from the open set
    openset.remove(current)
    #Add it to the closed set
    closedset.add(current)
    #Loop through the node's children/siblings
    for node in children(current,grid):
        #If it is already in the closed set, skip it
        if node in closedset:
            continue
        #Otherwise if it is already in the open set
        if node in openset:
            #Check if we beat the G score 
            new_g = current.G + current.move_cost(node)
            if node.G > new_g:
                #If so, update the node to have a new parent
                node.G = new_g
                node.parent = current
        else:
            #If it isn't in the open set, calculate the G and H score for the node
            node.G = current.G + current.move_cost(node)
            node.H = manhattan(node, goal)
            #Set the parent to our current item
            node.parent = current
            #Add it to the set
            openset.add(node)
    #Throw an exception if there is no path
    raise ValueError('No Path Found')
def next_move(pacman,food,grid):
#Convert all the points to instances of Node
for x in xrange(len(grid)):
    for y in xrange(len(grid[x])):
        grid[x][y] = Node(grid[x][y],(x,y))
#Get the path
path = aStar(grid[pacman[0]][pacman[1]],grid[food[0]][food[1]],grid)
#Output the path
print len(path) - 1
for node in path:
    x, y = node.point
    print x, y
pacman_x, pacman_y = [ int(i) for i in raw_input().strip().split() ]
food_x, food_y = [ int(i) for i in raw_input().strip().split() ]
x,y = [ int(i) for i in raw_input().strip().split() ]

grid = []
for i in xrange(0, x):
grid.append(list(raw_input().strip()))

next_move((pacman_x, pacman_y),(food_x, food_y), grid)
1
  • skipping neighbour which are already in closed set will give suboptimal. Trying it on this graph (Its a youtube video example, ignore the language) will give wrong answer.
    – itsjwala
    Nov 21, 2018 at 9:48
7

You can consider A* a guided version of Dijkstra. Meaning, instead of exploring all the nodes, you will use a heuristic to pick a direction.

To put it more concretely, if you're implementing the algorithms with a priority queue then the priority of the node you're visiting will be a function of the cost (previous nodes cost + cost to get here) and the heuristic estimate from here to the goal. While in Dijkstra, the priority is only influenced by the actual cost to nodes. In either case, the stop criterion is reaching the goal.

6

Dijkstra finds the minimum costs from the starting node to all others. A* finds the minimum cost from the start node to the goal node.

Therefore it would seem that Dijkstra would be less efficient when all you need is the minimum distance from one node to another.

5
  • 2
    This is not true. Standard Dijkstra is used to give the shortest path between two points.
    – Emil
    Aug 18, 2012 at 21:36
  • 5
    Please don't mislead, Dijkstra's gives result from s to all other vertices. Thus it works slower. Nov 11, 2013 at 9:28
  • I second @Emil comment. All you need to do is to stop when removing the destination node from the priority queue and you have the shortest path from the source to destination. This was the original algorithm actually.
    – seteropere
    Aug 26, 2016 at 3:06
  • More precisely: if a target is specified, Dijkstra's finds the shortest path to all nodes that lie on paths shorter than the path to the specified target. The purpose of the heuristic in A* is to prune some of these paths. The effectiveness of the heuristic determines how many are pruned. Feb 19, 2017 at 13:45
  • @seteropere, but what if your destination node is the last node that is searched? It is definitely less efficient, since A*'s heuristics and choosing a priority nodes are what helps make sure that the destination node searched is not the last node on the list Jun 28, 2017 at 14:18
5

BFS and Dijkstra’s algorithms are very similar to each other; they both are a particular case of the A* algorithm.

A* algorithm is not just more generic; it improves the performance of Dijkstra’s algorithm in some situations but this is not always true; in the general case, Dijkstra’s algorithm is asymptotically as fast as A*.

Dijkstra algorithm has 3 arguments. If you ever solved network delay time problem :

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:

A* method has extra 2 arguments:

 function aStar(graph, start, isGoal, distance, heuristic)
        queue ← new PriorityQueue()
        queue.insert(start, 0)

        # hash table to keep track of the distance of each vertex from vertex "start", 
        #that is, the sum of the weight of edges that needs to be traversed to get from vertex start to each other vertex. 
        # Initializes these distances to infinity for all vertices but vertex start .
        distances[v] ← inf (∀ v ε graph | v <> start)
      
       # hash table for the f-score of a vertex, 
       # capturing the estimated cost to be sustained to reach the goal from start in a path passing through a certain vertex. Initializes these values to infinity for all vertices but vertex "start".
        fScore[v] ← inf (∀ v ε graph | v <> start)

        # Finally, creates another hash table to keep track, for each vertex u, of the vertex through which u was reached.
        parents[v] ← null ( v ε graph)

A* takes two extra arguments, a distance function, and a heuristic. They both contribute to the computation of the so-called f-score. This value is a mix of the cost of reaching the current node u from the source and the expected cost needed in order to reach the goal from u.

By controlling these two arguments, we can obtain either BFS or Dijkstra’s algorithm (or neither). For both of them, the heuristic will need to be a function that is identically equal to 0 , something we could write like

   lambda(v) → 0 

Both of these algorithms, in fact, completely disregard any notion of or information about the distance of vertices to goal.

For the distance metrics, the situation is different:

  • Dijkstra’s algorithm uses the edge’s weight as a distance function, so we need to pass something like

      distance = lambda(e) → e.weight 
    
  • BFS only takes into account the number of edges traversed, which is equivalent to considering all edges to have the same weight, identically equal to 1! And thus, we can pass

      distance = lambda(e) → 1 
    

A* gains an advantage only in some contexts where we have extra information that we can somehow use. we can use A* to drive search faster to the goal is when we have information about the distance from all or some vertices to the goal.

enter image description here

Notice that in this particular case, the key factor is that the vertices, carry extra information with them (their position, which is fixed) that can help estimate their distance to the final goal. This isn’t always true and is usually not the case for generic graphs. To put it differently, the extra information here doesn’t come from the graph, but from domain knowledge.

The key, here and always, is the quality of the extra information 
captured by the Heuristic function: the more reliable and closer 
to real distance the estimate, the better A* performs.

Reference

3

If you look at the psuedocode for Astar :

foreach y in neighbor_nodes(x)
             if y in closedset
                 continue

Whereas, if you look at the same for Dijkstra :

for each neighbor v of u:         
             alt := dist[u] + dist_between(u, v) ;

So, the point is, Astar will not evaluate a node more than once,
since it believes that looking at a node once is sufficient, due
to its heuristics.

OTOH, Dijkstra's algorithm isn't shy of correcting itself, in case
a node pops up again.

Which should make Astar faster and more suitable for path finding.

3
  • 7
    This is not true: A* can look at nodes more than once. In fact, Dijkstra is a special-case of A*...
    – Emil
    Aug 18, 2012 at 21:37
  • 2
    Check this one for clarification: stackoverflow.com/questions/21441662/…
    – spiralmoon
    Feb 14, 2014 at 16:10
  • All search algorithms have a "frontier" and a "visited set". Neither algorithm corrects the path to a node once it is in the visited set: by design, they move nodes from the frontier to the visited set in priority order. Minimal known distances to nodes can be updated only while they are on the frontier. Dijkstra's is a form of best-first search, and a node will never be revisited once it is placed in the "visited" set. A* shares this property, and it uses an auxiliary estimator to choose which nodes on the frontier to prioritize. en.wikipedia.org/wiki/Dijkstra%27s_algorithm
    – pygosceles
    Feb 10, 2019 at 3:55
2

Dijkstra's algorithm finds the shortest path definitely. On the other hand A* depends on the heuristic. For this reason A* is faster than Dijkstra's algorithm and will give good results if you have a good heuristic.

2
  • 4
    A* gives the same results as Dijkstra, but faster when you use a good heuristic. A* algorithm imposes some conditions for to work correctly such as the estimated distance between current node and the final node should be lower than the real distance.
    – Alexandru
    Nov 15, 2009 at 22:36
  • 4
    A* is guaranteed to give the shortest path when the heuristic is admissible (always underestimates)
    – Robert
    May 22, 2010 at 23:14
0

In A*, for each node you check the outgoing connections for their .
For each new node you calculate the lowest cost so far (csf) depending on the weights of the connections to this node and the costs you had to reach the previous node.
Additionally you estimate the cost from the new node to the target node and add this to the csf. You now have the estimated total cost (etc). (etc = csf + estimated distance to target) Next you choose from the new nodes the one with the lowest etc.
Do the same as before until one of the new nodes will be the target.

Dijkstra works almost the same. Except that the estimated distance to target is always 0, and the algorithm first stops when the target is not only one of the new nodes, but also the one with the lowest csf.

A* is usually faster than dijstra, though this will not always be the case. In video games you often prefare the "close enough for a game" approach. Therefore the "close enough" optimal path from A* usually suffices.

-1

Dijkstra's algorithm is definitely complete and optimal that you will always find the shortest path. However it tends to take longer since it is used mainly to detect multiple goal nodes.

A* search on the other hand matters with heuristic values, which you can define to reach your goal nearer, such as manhattan distance towards goal. It can be either optimal or complete which depends on heuristic factors. it is definitely faster if you have a single goal node.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.