Python: Breadth First Search capable of returning largest distance?

Question

I have a dictionary representing a directed graph. For example...

myDict = {'foo': ['hello', 'stack'], 'bar' : ['over', 'flow']}

This means that the 'foo' node points to 'hello' and 'stack' while the 'bar' node points to 'over' and 'flow'.

I have also written code for performing a breadth first search to find the shortest path between any two nodes...

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

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?

tmyklebu tmyklebu · Accepted Answer · 2013-05-26T02:03:16

Your problem is called the "graph diameter problem."

Breadth-first search creates a breadth-first search tree. The longest tree path between two nodes is, in general, going to be longer than the longest path between them because of the presence of non-tree edges. So no, you can't get BFS to do that directly.

BFS will nail it for trees, but it's slightly nontrivial.

There's a variant called "lexicographic breadth-first search" that can find the diameter of some restricted classes of graphs. Those graph classes that I've run into where LBFS works tended to look a lot like trees.

EDIT: You can, of course, run BFS once starting from each node and figure out the longest of the paths that BFS reports. Or you could use the extremely elegant Floyd-Warshall algorithm.

Python: Breadth First Search capable of returning largest distance?

1 Answers