Get startedGet started for free

Shortest Path II

Now that you've got the code for checking whether the destination node is present in neighbors, next up, you're going to extend the same function to write the code for the condition where the destination node is not present in the neighbors.

All the code you need to write is in the else condition; that is, if node2 is not in neighbors.

This exercise is part of the course

Introduction to Network Analysis in Python

View Course

Exercise instructions

  • Using the .add() method, add the current node node to the set visited_nodes to keep track of what nodes have already been visited.
  • Add the neighbors of the current node node that have not yet been visited to queue. To do this, you'll need to use the .extend() method of queue together with a list comprehension. The .extend() method appends all the items in a given list.
    • The output expression and iterator variable of the list comprehension are both n. The iterable is the iterator of neighbors, and the conditional is if n is not in the visited nodes.

Hands-on interactive exercise

Have a go at this exercise by completing this sample code.

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 ____])
Edit and Run Code