CommencerCommencer gratuitement

Plus court chemin I

Vous pouvez tirer parti de ce que vous savez sur la recherche de voisins pour essayer de trouver des chemins dans un réseau. Un algorithme permettant de trouver un chemin entre deux nœuds est l’algorithme de recherche en largeur, ou "breadth-first search" (BFS). Avec BFS, vous partez d’un nœud donné et explorez itérativement ses voisins puis les voisins de ses voisins jusqu’à atteindre le nœud de destination.

Les algorithmes de recherche de chemin sont importants car ils offrent un autre moyen d’évaluer l’importance des nœuds ; vous le verrez dans un exercice ultérieur.

Dans cette série de 3 exercices, vous allez progresser pas à pas jusqu’à parvenir à l’algorithme BFS final. Le problème a été découpé en 3 parties qui, si vous les réalisez successivement, vous conduiront à une première implémentation de BFS.

Cet exercice fait partie du cours

Introduction à l’analyse de réseaux en Python

Afficher le cours

Instructions

  • Créez une fonction appelée path_exists() qui prend 3 paramètres — G, node1 et node2 — et renvoie si un chemin existe entre ces deux nœuds.
  • Initialisez la file des nœuds à visiter avec le premier nœud, node1. queue doit être une liste.
  • Itérez sur les nœuds de queue.
  • Récupérez les voisins du nœud en utilisant la méthode .neighbors() du graphe G.
  • Vérifiez si le nœud de destination node2 se trouve dans l’ensemble neighbors. Si oui, renvoyez True.

Exercice interactif pratique

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

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

    # Initialize the queue of nodes to visit with the first node: queue
    queue = ____

    # Iterate over the nodes in the queue
    for node in ____:

        # Get neighbors of the node
        neighbors = ____

        # Check to see if the destination node is in the set of neighbors
        if node2 in ____:
            print('Path exists between nodes {0} and {1}'.format(node1, node2))
            return ____
            break
Modifier et exécuter le code