What is correct way to implement A* algorithm? Do we update nodes in closedSet or not?

Question

As I in A* algorithm (A-star algorithm) we keep nodes in two lists: one priority queue and one regular array. The priority queue is called openSet, the other one is called closedSet.

'openSet' containts the nodes we are going to visit, closedSet are nodes we already visited.

Here's a pseudocode that implements A* algorithm:

openSet.add(startNode)
while not openSet.empty():
    currentNode = openSet.get()
  
    if currentNode == targetNode: # This is to stop searching when target is found
        break
    
    closedSet.add(currentNode)


    for neighborNode in currentNode.neighbors:
        if neighborNode not in openSet and not in closedSet:
            neighborNode.previousNode = currentNode   #building a path from currentNode to neighbor node
            neighborNode.g = currentNode.g + adjecentEdge.weight
            neighborNode.h = heuristic(neighborNode, targetNode)
            neighborNode.f = neighborNode.g + neighborNode.h
            openSet.add(neighborNode)
        else if neighborNode.g > currentNode.g + adjecentEdge.weight:
            neighborNode.previousNode = currentNode   #building a path from currentNode to neighbor node
            neighborNode.g = currentNode.g + adjecentEdge.weight
            neighborNode.h = heuristic(neighborNode, targetNode)
            neighborNode.f = neighborNode.g + neighborNode.h
                #Should I remove this part or not?
                if neighborNode in closedSet:
                    closedSet.remove(neighborNode)
                    openSet.add(neighborNode)


return getPath(startNode, targetNode)

In this code I do update nodes if it has less cost, I update whether it's a node in closedSet or not, and if it's a node in closedSet I remove that from closedSet and add it to openSet.

Do we update nodes in closedSet or not in A* algorithm?

I did implement both in Python, both does find the shortest path.

When I don't update nodes in closedSet it finds the path faster in my Graphs, but it may be just some coincidence.

Here's another pseudocode which doesn't update nodes in closedSet at all:

Here's a pseudocode that implements A* algorithm:

openSet.add(startNode)
while not openSet.empty():
    currentNode = openSet.get()
  
    if currentNode == targetNode: # This is to stop searching when target is found
        break
    
    closedSet.add(currentNode)


    for neighborNode in currentNode.neighbors:
        if neighborNode not in openSet and not in closedSet:
            neighborNode.previousNode = currentNode   #building a path from currentNode to neighbor node
            neighborNode.g = currentNode.g + adjecentEdge.weight
            neighborNode.h = heuristic(neighborNode, targetNode)
            neighborNode.f = neighborNode.g + neighborNode.h
            openSet.add(neighborNode)
        else if neighborNode not in closedSet and neighborNode.g > currentNode.g + adjecentEdge.weight:
            neighborNode.previousNode = currentNode   #building a path from currentNode to neighbor node
            neighborNode.g = currentNode.g + adjecentEdge.weight
            neighborNode.h = heuristic(neighborNode, targetNode)
            neighborNode.f = neighborNode.g + neighborNode.h

return getPath(startNode, targetNode)

When implementing A* algorithm do we update nodes in closedSet or not?

If we update nodes in closedSet, do we add them to openSet again?

Answer 1

If the heuristic is consistent, the nodes in the closed set will not need to be updated. If the heuristic is admissible but not consistent, the nodes in the closed set may need to be updated.

Most real-world heuristics are consistent, so most of the time that A* is implemented, that part of the algorithm is unnecessary and, for speed, not implemented at all.