ComeçarComece de graça

Shortest Path II

Agora que você já tem o código para verificar se o nó de destino está presente em neighbors, o próximo passo é estender a mesma função para escrever o código da condição em que o nó de destino não está presente em neighbors.

Todo o código que você precisa escrever está no bloco else; ou seja, se node2 não estiver em neighbors.

Este exercício faz parte do curso

Introdução à Análise de Redes em Python

Ver curso

Instruções do exercício

  • Usando o método .add(), adicione o nó atual node ao conjunto visited_nodes para acompanhar quais nós já foram visitados.
  • Adicione os neighbors do nó atual node que ainda não foram visitados à queue. Para fazer isso, você precisará usar o método .extend() de queue junto com uma list comprehension. O método .extend() adiciona todos os itens de uma lista fornecida.
    • A expressão de saída e a variável iteradora da list comprehension são ambas n. O iterável é o iterador de neighbors, e a condicional é se n não estiver nos nós visitados.

Exercício interativo prático

Experimente este exercício completando este código de exemplo.

def path_exists(G, node1, node2):
    """
    This function checks whether a path exists between two nodes (node1, node2) in graph G.
    """
    visited_nodes = set()
    queue = [node1]

    for node in queue:
        neighbors = G.neighbors(node)
        if node2 in neighbors:
            print('Path exists between nodes {0} and {1}'.format(node1, node2))
            return True

        else:
            # Add current node to visited nodes
            ____

            # Add neighbors of current node that have not yet been visited
            queue.extend([____ for ____ in ____ if ____ not in ____])
Editar e executar o código