Passo 17

Instruções

Antes de tentar atualizar a distância para um vizinho, você precisa verificar se o vizinho é alcançável e não visitado. Então você calculará qual seria a distância total para alcançar esse vizinho através do nó atual. Dentro do loop for, adicione uma declaração if que verifica:

A distance não é igual a INF (significando que há uma aresta entre os nós)
O vizinho node_no ainda não foi visitado

Dentro do bloco if, crie uma variável chamada new_distance e atribua a soma de distances[current] (a menor distância para o nó atual) e distance (a distância do nó atual para o vizinho).

O que fazer:

Testes:

Você deve ter uma declaração `if` que verifica se `distance` não é igual a `INF` e se o nó vizinho não foi visitado.
Você deve criar uma variável chamada `new_distance` dentro do bloco `if`.
Você deve atribuir a `new_distance` a soma de `distances[current]` e `distance`.

INF = float('inf')
adj_matrix = [
    [0, 5, 3, INF, 11, INF],
    [5, 0, 1, INF, INF, 2],
    [3, 1, 0, 1, 5, INF],
    [INF, INF, 1, 0, 9, 3],
    [11, INF, 5, 9, 0, INF],
    [INF, 2, INF, 3, INF, 0],
]

def shortest_path(matrix, start_node, target_node=None):
    n = len(matrix)
    distances = [INF] * n
    distances[start_node] = 0
    paths = [[node_no] for node_no in range(n)]
    visited = [False] * n

    for _ in range(n):
        min_distance = INF
        current = -1
        for node_no in range(n):
            if not visited[node_no] and distances[node_no] < min_distance:
              min_distance = distances[node_no]
              current = node_no

        if current == -1:
            break
        visited[current] = True


        for node_no in range(n):  
            distance = matrix[current][node_no]

Preview