pythondesign-patternsiterableobject-type

'NoneType' object is not iterable error in Python


I am trying to find the shortest list inside of the Paths list but I receive an error ('NoneType' object is not iterable error in Python). This function is for "graph pattern" or "searching algorithm" finding the shortest path to a goal. Please let me know what I am doing wrong here. Thanks!

graph = {'A':['B','C'],'B':['F','D','I'],'C':['D','E','G'],'D':['H'],'F':['I'],'E':['G'],'I':['H'],'D':['H'],'H':['G']} 




def find_all_paths(graph, start, end, path=[]):

        path = path + [start]
        if start == end:
            return [path]
        if start not in graph:
            return []
        paths = []
        for node in graph[start]:
            if node not in path:
                newpaths = find_all_paths(graph, node, end, path)
                for newpath in newpaths:
                    paths.append(newpath)

        minList=min(paths, key= len)
        print(minList)



Solution

  • The vertex G has been missed out from your adjacency list. After modifying your adjacency list and returning paths from the function, you would be able to get the correct result

    graph = {'A':['B','C'],'B':['F','D','I'],'C':['D','E','G'],'D':['H'],'F':['I'],'E':['G'],'I':['H'],'D':['H'],'H':['G'], 'G':[]} 
    
    def find_all_paths(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        paths = []
        for node in graph[start]:
            if node not in path:
                newpaths = find_all_paths(graph, node, end, path)
                if newpaths:
                    for newpath in newpaths:
                        paths.append(newpath)
        return paths
    
    graph
    
    {'A': ['B', 'C'],
     'B': ['F', 'D', 'I'],
     'C': ['D', 'E', 'G'],
     'D': ['H'],
     'F': ['I'],
     'E': ['G'],
     'I': ['H'],
     'H': ['G'],
     'G': []}
    
    paths = find_all_paths(graph,'A', 'H',[])
    

    Output :

    paths 
    
    [['A', 'B', 'F', 'I', 'H'],
     ['A', 'B', 'D', 'H'],
     ['A', 'B', 'I', 'H'],
     ['A', 'C', 'D', 'H']]
    

    For finding one of the shortest paths, you can use

    min(paths, key=len)