Não queremos menos passos. Queremos menor custo.

Usando o mesmo grafo da aula anterior, queremos sair de A e chegar em G pagando o menor custo possível.

O algoritmo repete três ideias simples:

Suponha que já sabemos que o custo para chegar em B é 4.

import heapq


grafo = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('D', 5), ('E', 1)],
    'C': [('A', 2), ('E', 7), ('F', 3)],
    'D': [('B', 5), ('G', 6)],
    'E': [('B', 1), ('C', 7), ('G', 2)],
    'F': [('C', 3), ('G', 4)],
    'G': [('D', 6), ('E', 2), ('F', 4)]
}


def dijkstra(grafo, origem):

    # No início, somente a distância da origem é conhecida.
    dist = {
        vertice: float('inf')
        for vertice in grafo
    }

    anterior = {
        vertice: None
        for vertice in grafo
    }

    dist[origem] = 0

    # (distância, vértice)
    fila = [(0, origem)]

    while fila:

        # A fila de prioridade retira o menor custo acumulado.
        distancia_atual, v = heapq.heappop(fila)

        # Entrada antiga da fila?
        if distancia_atual > dist[v]:
            continue

        for vizinho, peso in grafo[v]:

            novo_custo = distancia_atual + peso

            # Relaxamento
            if novo_custo < dist[vizinho]:

                dist[vizinho] = novo_custo
                anterior[vizinho] = v

                # A nova estimativa volta para a fila e será
                # processada quando for a menor disponível.
                heapq.heappush(
                    fila,
                    (novo_custo, vizinho)
                )

    return dist, anterior


# Executa o algoritmo completo a partir de A.
dist, anterior = dijkstra(grafo, 'A')

print(dist['G'])