Kom igångKom igång gratis

Kortaste vägen II

Nu när du har koden för att kontrollera om målnoden finns bland grannarna är nästa steg att utöka samma funktion med kod för det fall då målnoden inte finns bland grannarna.

All kod du behöver skriva finns i else-villkoret, det vill säga när node2 inte finns i neighbors.

Den här övningen är en del av kursen

Introduktion till nätverksanalys i Python

Visa kurs

Övningsinstruktioner

  • Använd .add()-metoden för att lägga till den aktuella noden node i mängden visited_nodes, så att du håller reda på vilka noder som redan har besökts.
  • Lägg till de grannar till den aktuella noden node som ännu inte har besökts i queue. För att göra detta behöver du använda .extend()-metoden på queue tillsammans med en listomfattning. .extend()-metoden lägger till alla element från en given lista.
    • Både utdatuttrycket och iteratorvariabeln i listomfattningen är n. Det iterbara är iteratorn för neighbors, och villkoret är att n inte finns i de besökta noderna.

Interaktiv övning med praktiskt arbete

Testa den här övningen genom att slutföra den här exempelkoden.

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 ____])
Redigera och kör kod