

In [16]:

    
import sys
        
    
def find_shortest_paths(graph, start, end, path=None):
    
    path = path or []
    path = path + [start]
    
    if start == end:
        return [path]
    
    if not graph.has_key(start):
        return None
    
    shortest = []
    
    for node in graph[start]:
        if node not in path:
            newpath = find_shortest_paths(graph, node, end, path)
            if newpath:
                if not shortest or len(newpath[0]) < len(shortest[0]):
                    shortest = newpath
                elif len(newpath[0]) == len(shortest[0]):
                    shortest += newpath
              
    return shortest
                
        
example_graph = {
    u'Frankfurt': [u'Mannheim', u'Würzburg', u'Kassel'],
    u'Mannheim': [u'Frankfurt', u'Karlsruhe'],
    u'Karlsruhe': [u'Augsburg', u'München'],
    u'Augsburg': [u'München', u'Karlsruhe'],
    u'München': [u'Würzburg', u'Augsburg', u'Nürnberg', u'Kassel'],
    u'Nürnberg': [u'München', u'Stuttgart', u'Würzburg'],
    u'Stuttgart': [u'Nürnberg'],
    u'Kassel': [u'München', u'Frankfurt'],
    u'Würzburg': [u'München', u'Nürnberg', u'Frankfurt', u'Erfurt'],
    u'Erfurt': [u'Würzburg'],
}


find_shortest_paths(example_graph, u'Frankfurt', u'München')









    Out[16]:





[[u'Frankfurt', u'W\xfcrzburg', u'M\xfcnchen'],
 [u'Frankfurt', u'Kassel', u'M\xfcnchen']]



In [17]:

    
%%timeit
find_shortest_paths(example_graph, u'Frankfurt', u'München')









    



100000 loops, best of 3: 9.82 µs per loop

Shortest Paths