Passo 23

Instruções

Agora que você determinou que um nó deve ser exibido, você precisa formatar seu caminho para que ele possa ser impresso claramente. Para isso você usará uma expressão geradora. Uma expressão geradora é semelhante a uma compreensão de lista, mas em vez de criar uma lista, ela gera cada valor um de cada vez. Ela usa parênteses () em vez de colchetes []. Por exemplo:

numbers = [1, 2, 3]
squared = (x**2 for x in numbers)  # Generator expression

Dentro do loop após a instrução if, crie uma variável chamada string_path. Atribua a ela uma expressão geradora que converte cada número de nó em paths[node_no] para uma string usando str(). A expressão geradora deve iterar sobre cada número de nó n em paths[node_no].

O que fazer:

Testes:

Você deve criar uma variável chamada `string_path`.
Você deve atribuir uma expressão geradora a `string_path`.
Sua expressão geradora deve iterar sobre `paths[node_no]`.
Sua expressão geradora deve usar `n` como a variável de iteração para iterar sobre `paths[node_no]`.
Sua expressão geradora deve avaliar `str(n)` para cada `n` em `paths[node_no]`.

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]
            if distance != INF and not visited[node_no]:
                new_distance = distances[current] + distance
                if new_distance < distances[node_no]:
                    distances[node_no] = new_distance
                    paths[node_no] = paths[current] + [node_no]


    targets = [target_node] if target_node is not None else range(n)
    for node_no in targets:
        if node_no == start_node or distances[node_no] == INF:
            continue

Preview