CommencezCommencez gratuitement

Plus court chemin I

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

Les algorithmes de recherche de chemin sont importants, car ils offrent une autre façon d'évaluer l'importance des nœuds; vous le verrez dans un prochain exercice.

Dans cette série de 3 exercices, vous allez progresser graduellement jusqu'à l'algorithme BFS final. Le problème a été découpé en 3 parties qui, si vous les complétez à la suite, vous mèneront à une première implémentation de l'algorithme BFS.

Cette activité fait partie du cours

Introduction à l'analyse des réseaux en Python

Voir le cours

Instructions de l’exercice

  • Créez une fonction appelée path_exists() qui prend 3 paramètres — G, node1 et node2 — et qui retourne si un chemin existe ou non entre les deux nœuds.
  • Initialisez la file d'attente des nœuds à visiter avec le premier nœud, node1. queue doit être une liste.
  • Itérez sur les nœuds dans queue.
  • Obtenez les voisins du nœud à l'aide de la méthode .neighbors() du graphe G.
  • Vérifiez si le nœud de destination node2 fait partie de l'ensemble neighbors. Si oui, retournez True.

Exercice interactif pratique

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

# 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