title: Python: Breadth First Search capable of returning largest distance?
body: <p>I have a dictionary representing a directed graph. For example...</p>
  
  <pre><code>myDict = {'foo': ['hello', 'stack'], 'bar' : ['over', 'flow']}
  </code></pre>
  
  <p>This means that the <strong>'foo'</strong> node points to <strong>'hello'</strong> and <strong>'stack'</strong> while the <strong>'bar'</strong> node points to <strong>'over'</strong> and <strong>'flow'</strong>.</p>
  
  <p>I have also written code for performing a breadth first search to find the <em>shortest</em> path between any two nodes...</p>
  
  <pre><code>from collections import deque
  
  def breadthFirstSearch(graph, start, end):
      q = deque()
      path = (start, )
      q.append(path)
      visited = set([start])
      while q:
          path = q.popleft()
          last_node = path[-1]
          if last_node == end:
              return path
          for node in graph[last_node]:
              if node not in visited:
                  visited.add(node)
                  q.append(path + (node,))
      print 'There is no path from ' + start + ' to ' + end + '.'
      return None
  </code></pre>
  
  <p>My question is: Is it possible to modify this breadth first search so as it gives me the largest shortest path and the start and end nodes for that path?</p>