IniziaInizia gratis

Shortest Path II

Ora che hai scritto il codice per verificare se il nodo di destinazione è presente tra i vicini, estenderai la stessa funzione per gestire il caso in cui il nodo di destinazione non sia presente tra i vicini.

Tutto il codice che devi scrivere è nel blocco else; cioè, se node2 non è in neighbors.

Questo esercizio fa parte del corso

Introduzione all'analisi delle reti in Python

Visualizza il corso

Istruzioni dell'esercizio

  • Usando il metodo .add(), aggiungi il nodo corrente node all'insieme visited_nodes per tenere traccia dei nodi già visitati.
  • Aggiungi a queue i vicini del nodo corrente node che non sono ancora stati visitati. Per farlo, devi usare il metodo .extend() di queue insieme a una list comprehension. Il metodo .extend() aggiunge tutti gli elementi di una lista.
    • L'espressione di output e la variabile iteratore della list comprehension sono entrambe n. L'iterabile è l'iteratore di neighbors e la condizione è che n non sia tra i nodi visitati.

Esercizio pratico interattivo

Prova a risolvere questo esercizio completando il codice di esempio.

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 ____])
Modifica ed esegui il codice