A* algorithm change node parent

Question

I am confused about changing the parent of a node in the A* algorithm. There seem to be different ways of choosing a new parent:

In this video: https://www.youtube.com/watch?v=KNXfSOx4eEE

It says that you should check this:

 G cost currentNode + movement cost from currentNode <= G cost openListNode 

If that is the case then we should replace the parent node of the openListNode to the current node.

But in this implementation: http://www.codebytes.in/2015/02/a-shortest-path-finding-algorithm.html

it has the following code:

static void checkAndUpdateCost(Cell current, Cell t, int cost){
    if(t == null || closed[t.i][t.j])return;
    int t_final_cost = t.heuristicCost+cost;

    boolean inOpen = open.contains(t);
    if(!inOpen || t_final_cost<t.finalCost){
        t.finalCost = t_final_cost;
        t.parent = current;
        if(!inOpen)open.add(t);
    }
}

It checks the final cost which is : G + H , which contradicts the other explanation, as it should be only G cost, not the sum of the G cost and the heuristic.

Can someone explain me, which one is correct ?, is the implementation wrong ?

Answer 1

Bottom Line Up Front (BLUF):

The video is accurate, but here's the key: The node's parent should only be updated in one of the following two cases: 1.) when encountering the node for the first time, or 2.) when you find a more efficient path to a node that was previously encountered. Also, do not use the heuristic when updating a node's parent.

Additional Details:

Below is a working implementation based on Wikipedia's Pseudocode; I've added extra comments to differentiate the two cases.

If !isOpen && !isClosed is true then the node has never been seen before; therefore, it's parent should be set to the current node, and it should be added to the open set. But if !isOpen && !isClosed is false, then the node was already in the open set (i.e. if isOpen is true) or if it was previously closed (i.e. if isClosed is true). Therefore, we need to check if the current path is more efficient than the one which previously caused the neighbor node to be in the open/closed set-- this is why we check if costFromStart < g_score[neighborNode.x][neighborNode.y]

while (!openList.isEmpty()) {
    Pair node = openList.dequeueMin().getValue();

    if (node.equals(goal)) {
        // construct the path from start to goal
        return reconstruct_path(goal);
    }

    for (Pair neighborNode : getNeighbors(node,goal)) {
        if (neighborNode == null) continue;
        boolean isOpen = openSet.contains(neighborNode);
        boolean isClosed = closedSet.contains(neighborNode);
        double costFromStart = g_score[node.x][node.y]+MOVEMENT_COST;

        // check if the neighbor node has not been
        // traversed or if a shorter path to this
        // neighbor node is found.
        if (
            (!isOpen && !isClosed) // first time node has been encountered
                || //or
            costFromStart < g_score[neighborNode.x][neighborNode.y]) //new path is more efficient
        {
            came_from[neighborNode.x][neighborNode.y] = node;
            g_score[neighborNode.x][neighborNode.y] = costFromStart;
            h_score[neighborNode.x][neighborNode.y] =
                    estimateCost(neighborNode,goal);
            if (isClosed) {
                closedSet.remove(neighborNode);
            }
            if (!isOpen) {
                openList.enqueue(neighborNode,costFromStart);
                openSet.add(neighborNode);
            }
        }
    }
    closedSet.add(node);
}