CommencerCommencer gratuitement

Chemin le plus court III

Voici le dernier exercice de cette série ! Vous allez maintenant terminer le problème en écrivant le code qui renvoie False s’il n’y a aucun chemin entre deux nœuds.

Cet exercice fait partie du cours

Introduction à l’analyse de réseaux en Python

Afficher le cours

Instructions

  • Vérifiez si la file d’attente a été vidée. Vous pouvez le faire en inspectant le dernier élément de la file avec [-1].
  • Placez l’instruction de retour appropriée pour indiquer s’il existe un chemin entre ces deux nœuds.

Exercice interactif pratique

Essayez cet exercice en complétant cet exemple de code.

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 = list(G.neighbors(node))
        if node2 in neighbors:
            print('Path exists between nodes {0} and {1}'.format(node1, node2))
            return True
            break

        else:
            visited_nodes.add(node)
            queue.extend([n for n in neighbors if n not in visited_nodes])

        # Check to see if the final element of the queue has been reached
        if node == ____:
            print('Path does not exist between nodes {0} and {1}'.format(node1, node2))

            # Place the appropriate return statement
            return ____
Modifier et exécuter le code