ComenzarEmpieza gratis

Shortest Path II

Ahora que ya tienes el código para comprobar si el nodo de destino está presente en los vecinos, el siguiente paso es ampliar la misma función para escribir el código del caso en que el nodo de destino no está presente en los vecinos.

Todo el código que necesitas escribir está en la condición else; es decir, si node2 no está en neighbors.

Este ejercicio forma parte del curso

Introducción al análisis de redes en Python

Ver curso

Instrucciones del ejercicio

  • Usando el método .add(), añade el nodo actual node al conjunto visited_nodes para llevar un registro de qué nodos ya se han visitado.
  • Añade a queue los vecinos del nodo actual node que aún no se hayan visitado. Para ello, tendrás que usar el método .extend() de queue junto con una comprensión de listas. El método .extend() agrega todos los elementos de una lista dada.
    • La expresión de salida y la variable iteradora de la comprensión de listas son ambas n. El iterable es el iterador de neighbors, y la condición es si n no está en los nodos visitados.

Ejercicio interactivo práctico

Prueba este ejercicio y completa el código de muestra.

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 ____])
Editar y ejecutar código