shortest path from goal to root in directed graph with cycles python
Question: I want to find the shortest path from `goal` to `root` working backwards

My input for `root` is `{'4345092': ['6570646', '40586', '484']}` My input for
`goal` is `{'886619': ['GOAL']}`

My input for `path_holder` is an input but it gets converted to `dct` and is
used for this function. I am getting stuck regarding the while loop as it
creates the path for me backwards. Right now I can't get `q` to print because
that part of the code isn't being ran. `dct` is basically a directed graph
representation that contains cycles. I can't seem to figure out how to start
from `GOAL` and end up at the `root` node. I was wondering if someone could
help me figure this out thanks!

dct:

    
    
    dct = 
    { '612803266': ['12408765', '46589', '5880', '31848'], 
      '8140983': ['7922972', '56008'],
      '7496838': ['612803266'], 
      '1558536111': ['7496838'], 
      '31848': ['DEADEND'], 
      '1910530': ['8140983'], 
      '242010': ['58644', '886619'], 
      '727315568': ['DEADEND'], 
      '12408765': ['DEADEND'], 
      '56008': ['DEADEND'], 
      '58644': ['DEADEND'], 
      '886619': ['GOAL'], 
      '40586': ['931', '727315568', '242010', '1910530'], 
      '5880': ['1558536111'], 
      '46589': ['DEADEND'], 
      '6570646': ['2549003','43045', '13830'],
      '931': ['299159122'],
      '484': ['1311310', '612803266'],
      '1311310': ['DEADEND'],
      '7922972': ['DEADEND']
      }
    

my function:

    
    
    def backtrace(path_holder, root, goal):
        dct = {}
        for d in path_holder:
                dct.update(d)
        rootnode = root.keys()[0]
        goal = goal.keys()[0]
        path = []
        path.append(goal)
        q = 0
        while goal != rootnode: 
            # find key that contains goal in list
            for i in dct:   #iterate keys
                if i in dct:    # prevent repeat of path
                    continue
                for j in dct[i]:    #iterate though children
                    if j == goal:
                        path.append(i)
                        goal = i    # look for new goal
                        q += 1
                        print q
                        #print goal
    
            # append key that has goal in the list
            # set goal to be the key that was appended
            # repeat
    
        return path
    


Answer: Just find the paths and then invert them.

**UPDATED:** Added "[]" to "DEADEND" and "GOAL" in end conditions.

    
    
    import copy as cp
    
    DCT = {...}  # You already know what goes here. 
    
    FOUND_PATHS = []            # In case of more than one path to GOAL.
    FOUND_REVERSE_PATHS = []
    
    COUNTER = len(DCT)
    
    def back_track(root, target_path = [], counter=COUNTER):
        """
        @param root: DCT key.
        @type root: str.
    
        @param target_path: Reference to the path we are constructing.
        @type target_path: list.
    
        """
        global FOUND_PATHS
    
        # Avoiding cycles.
        if counter == 0:
            return
    
        # Some nodes aren't full generated.
        try:
            DCT[root]
        except KeyError:
            return
    
        # End condition.
        if DCT[root] == ['DEADEND']:
            return
        # Path found.
        if DCT[root] == ['GOAL']:
            FOUND_PATHS.append(target_path)             # The normal path.
            reverse_path = cp.copy(target_path)
            reverse_path.reverse()
            FOUND_REVERSE_PATHS.append(reverse_path)     # The path you want.
            return
    
        for node in DCT[root]:
            # Makes copy of target parh and add the node.
            path_copy = cp.copy(target_path)
            path_copy.append(node)
            # Call back_track with current node and the copy 
            # of target_path.
            back_track(node, path_copy, counter=(counter - 1))
    
    if __name__ == '__main__':
        back_track('4345092')
        print(FOUND_PATHS)
        print(FOUND_REVERSE_PATHS) 
    

