CommencezCommencez gratuitement

Shortest Path II

Maintenant que vous avez le code pour vérifier si le nœud de destination est présent dans neighbors, vous allez prolonger la même fonction pour écrire le code du cas où le nœud de destination n'est pas présent parmi les neighbors.

Tout le code que vous devez écrire se trouve dans la condition else ; c'est-à-dire si node2 ne se trouve pas dans neighbors.

Cette activité fait partie du cours

Introduction à l'analyse des réseaux en Python

Voir le cours

Instructions de l’exercice

  • Avec la méthode .add(), ajoutez le nœud courant node à l'ensemble visited_nodes pour garder la trace des nœuds déjà visités.
  • Ajoutez à queue les neighbors du nœud courant node qui n'ont pas encore été visités. Pour ce faire, vous devrez utiliser la méthode .extend() de queue avec une compréhension de liste. La méthode .extend() ajoute tous les éléments d'une liste donnée.
    • L'expression de sortie et la variable d'itération de la compréhension de liste sont toutes deux n. L'itérable est l'itérateur de neighbors, et la condition est que n ne soit pas dans les nœuds visités.

Exercice interactif pratique

Essayez cet exercice en complétant ce code d’exemple.

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 ____])
Modifier et exécuter le code