Začněte nyníZačněte zdarma

Nejkratší cesta II

Teď, když máš hotový kód pro případ, kdy je cílový uzel přítomen v sousedech, rozšíříš stejnou funkci o kód pro případ, kdy cílový uzel v sousedech není.

Veškerý kód, který potřebuješ napsat, patří do větve else – tedy do situace, kdy node2 není v neighbors.

Toto cvičení je součástí kurzu

Úvod do analýzy sítí v Pythonu

Zobrazit kurz

Pokyny k cvičení

  • Pomocí metody .add() přidej aktuální uzel node do množiny visited_nodes, aby bylo možné sledovat, které uzly už byly navštíveny.
  • Přidej do queue ty sousedy aktuálního uzlu node, které ještě nebyly navštíveny. K tomu použij metodu .extend() proměnné queue spolu s list comprehension. Metoda .extend() připojí všechny prvky zadaného seznamu.
    • Výstupní výraz i iterační proměnná list comprehension jsou oba n. Iterovatelný objekt je iterátor neighbors a podmínka říká, že n není v navštívených uzlech.

Interaktivní cvičení na vyzkoušení si v praxi

Vyzkoušejte si toto cvičení dokončením tohoto ukázkového kódu.

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 ____])
Upravit a spustit kód