all_paths_recursive.py

def r_dfs(current: Node, end: Node, all_paths: Set, visited=set(), current_path=[]):
    visited.add(current)
    current_path.append(current)
    
    if current == end:
        all_paths.add(tuple(current_path))  # Shallow copy
    else:
        for neighbour in current.neighbours() - visited:
            r_dfs(neighbour, end, all_paths, visited, current_path)
            
    current_path.pop()
    visited.remove(current)


def find_paths(start: Node, end: Node):
    all_paths = set()
    r_dfs(start, end, all_paths)
    return all_paths

shortest_path_iterative.py

def dfs(start: Node):
    stack = [(None, start)]
    visited = {start}

    while len(stack) > 0:
        parent, current = stack.pop()
        yield parent, current, visited
        new_children = current.neighbours() - visited
        stack += ((current, child) for child in new_children)
        visited |= new_children
  
 
def shortest_path(start: Node, end: Node):
    paths = {None: []}  # {destination: [path]}

    for parent, child, visited in dfs(start):
        paths[child] = paths[parent] + [child]

        if child == end:
            yield paths[child]

    return None  # or raise appropriate exception