IniziaInizia gratis

Shortest Path I

Puoi sfruttare ciò che sai sul trovare i vicini per provare a trovare percorsi in una rete. Un algoritmo per cercare un percorso tra due nodi è il "breadth-first search" (BFS). Con un BFS parti da un nodo specifico e cerchi in modo iterativo tra i suoi vicini e i vicini dei vicini finché non trovi il nodo di destinazione.

Gli algoritmi di pathfinding sono importanti perché offrono un altro modo per valutare l'importanza dei nodi; lo vedrai in un esercizio successivo.

In questo set di 3 esercizi, ci arriverai passo dopo passo fino all'algoritmo BFS finale. Il problema è stato suddiviso in 3 parti che, se completate in successione, ti porteranno a una prima implementazione dell'algoritmo BFS.

Questo esercizio fa parte del corso

Introduzione all'analisi delle reti in Python

Visualizza il corso

Istruzioni dell'esercizio

  • Crea una funzione chiamata path_exists() che abbia 3 parametri - G, node1 e node2 - e restituisca se esiste o meno un percorso tra i due nodi.
  • Inizializza la coda dei nodi da visitare con il primo nodo, node1. queue deve essere una lista.
  • Itera sui nodi in queue.
  • Ottieni i vicini del nodo usando il metodo .neighbors() del grafo G.
  • Verifica se il nodo di destinazione node2 è nell'insieme dei neighbors. Se sì, restituisci True.

Esercizio pratico interattivo

Prova a risolvere questo esercizio completando il codice di esempio.

# 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
Modifica ed esegui il codice