A* contre Dijkstra, le match mesuré

def a_etoile_grille(p: int, q: int, depart: tuple, cible: tuple):
    def h(x):
        return abs(x[0] - cible[0]) + abs(x[1] - cible[1])
    dist = {depart: 0}
    figes = set()
    candidats = {depart}
    while candidats:
        # Priorité f(x) = dist[x] + h(x)
        s = min(candidats, key=lambda x: (dist[x] + h(x), h(x)))
        candidats.remove(s)
        figes.add(s)
        if s == cible:
            return dist[s], len(figes)
        (i, j) = s
        for v in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
            if 0 <= v[0] < p and 0 <= v[1] < q and v not in figes:
                if v not in dist or dist[s] + 1 < dist[v]:
                    dist[v] = dist[s] + 1
                    candidats.add(v)
    return None, len(figes)

Sur une grille vide $100\times 100$, Dijkstra fige l'intégralité des 10 000 cases de la grille. L'algorithme A* avec Manhattan ne fige que 199 cases (un chemin linéaire direct), car le terme d'heuristique cible immédiatement la bonne direction.