Como funciona esta versão específica do algoritmo A-star (manualmente, sem usar código em um PC)?

Eu estava fazendo um curso de IA quando me deparei com este problema no algoritmo A*:

As heurísticas são as seguintes:

          N : h(N)

         'A': 9,
         'B': 10,
         'C': 13,
         'D': 9,
         'E': 17,
         'F': 4,
         'G': 0,
         'H': 9,
         'I': 11,
         'J': 2,
         'K': 5,
         'L': 14,
         'M': 4,
         'N': 6,
         'O': 11,
         'P': 4,
         'Q': 4,
         'R': 6,
         'S': 12

O nó inicial é 'S' e o nó objetivo é 'G'. Os custos entrenós estão especificados na imagem em vermelho. A resposta oficial é o caminho 'SCDFJG' com custo = 26. A ordem de inspeção do nó é dada como: S,I,C,D,F,H,K,J.

Pelo meu entendimento, a cada etapa escolhemos e expandimos um nó de acordo com o valor da heurística f = g + h, onde g é o custo do movimento do nó 'S' até o nó determinado ao longo do caminho para chegar lá. Para os casos de valor g igual, o desempate deve estar na ordem alfabética dos nós do problema original.

Tentativas falhas

S -> {C,H,I,K}
argmin(f{SC,SH,SI,SK}) = SI
I -> {N,O,L,E}
argmin(f{SIN,SIO,SIL,SIE}) = SIN
.
.
.
path = SINRQG
cost = 36

Seguindo o procedimento acima, tentei A* ponderado (peso W = 3) em que f = g + 3*h, e obtive:

path = SKHFJG
cost = 48

Neste caso a resposta oficial é o caminho SINRQG! Agora, no problema original (w = 1), quando aplico o algoritmo de Dijkstra com f como heurística decisiva no lugar apenas de g, o custo é 26 e a ordem de inspeção é S,I,N,K,H,C ,D,F,J,G. Então, como faço para usar A* manualmente? Depois de algum trabalho consegui obter a versão do código da solução do curso:

from collections import deque

class Graph:
    

    def __init__(self, adjacency_list):
        self.adjacency_list = adjacency_list

    def get_neighbors(self, v):
        return self.adjacency_list[v]

    # heuristic function with equal values for all nodes, H[n]
.....
def a_star_algorithm(self, start_node, stop_node):
        open_list = set([start_node])
        closed_list = set([])
        g = {}
        g[start_node] = 0
        parents = {}
        parents[start_node] = start_node
        W = 3 #weight

        while len(open_list) > 0:
            n = None

            # Printing open and closed lists
            print(f"Open List: {open_list}")
            print(f"Closed List: {closed_list}")

            for v in open_list:
                if n is None or (g[v] + W*self.h(v)[0], v) < (g[n] + W*self.h(n)[0], n):
                    n = v;

            if n is None:
                print('Path does not exist!')
                return None

            if n == stop_node:
                reconst_path = []
                while parents[n] != n:
                    reconst_path.append(n)
                    n = parents[n]
                reconst_path.append(start_node)
                reconst_path.reverse()
                print('Path found:', reconst_path)
                return reconst_path

            for (m, weight) in self.get_neighbors(n):
                if m not in open_list and m not in closed_list:
                    open_list.add(m)
                    parents[m] = n
                    g[m] = g[n] + weight
                    print(f"Inspecting node {m}")
                    print(g[m]+W*self.h(m)[0])

                else:
                    if g[m] > g[n] + weight:
                        g[m] = g[n] + weight
                        parents[m] = n
                        if m in closed_list:
                            closed_list.remove(m)
                            open_list.add(m)

            open_list.remove(n)
            closed_list.add(n)

        print('Path does not exist!')
        return None

# Test your modified A* algorithm
adjacency_list = {
.......

No entanto, acho isso muito desajeitado para entender e implementar manualmente, embora dê a resposta correta.