Shortest Path From Goal To Root In Directed Graph With Cycles Python

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 inpu

Solution 1:

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)

defback_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.returnfor 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)