Find all paths in a graph

Question

My code does a DFS on the given graph and prints all possible paths for a given start and end node. My question is how can this be improved?

1. Can some form of memoization be used here? There are cases where a path from a certain source - destination is already found and will be an intermediate path for a different source - destination but it is still computed again.
2. As it is a generator will that make memoization different?
3. Is there an already existing text book algorithm that I am missing? Does not have to be specifically DFS.
4. Pythonic / Idiomatic code suggestions are also welcome.

This is my code

from itertools import product

def find_path(g, src, dst):
    """Prints all possible path for a graph `g` for all pairs in `src` and `dst`
    
    Args:
        g (list): 2d list, graph
        src (list): list of nodes that will be the source
        dst (list): list of nodes that will be the destination
    """

    graph = {}

    # constructing a graph
    for from_, to_ in g:
        graph.setdefault(from_, set()).add(to_)
        graph.setdefault(to_, set()).add(from_) # undirected

    def dfs(src, dst, path, seen):
        """Recursive generator that yields all paths from `src` to `dst`
        
        Args:
            src (int): source node
            dst (int): destination node
            path (list): path so far
            seen (set): set of visited nodes
        
        Yields:
            list: all paths from `src` to `dst`
        """
        if src in seen:
            return

        if src == dst:
            yield path + [src]
            return

        seen.add(src)

        for i in graph.get(src, []):
            yield from dfs(i, dst, path + [src], seen)
        seen.remove(src)


    # start finding path for all `src` `dst` pairs
    for source, destination in product(src, dst):
        print(source, destination, list(dfs(source, destination, [], set())))


g = list(product(range(1, 5), repeat=2)) # a graph for testing purpose
src = dst = range(1, 5) # source and destination, in actual code this will be a list
find_path(g, src, dst)

Answer 1

1. I don't think memoization will be useful here. Any correct algorithm is going to be O(n!), nothing you do can reduce that fundamentally because you still have to output all the paths.
   Trying to cache stuff you already output is just going to make the space-costs worse, it won't make the processing-time any better.
2. The advantages of using a generator are that the caller doesn't have to wait for the whole computation to finish before handling the early outputs, and that we never have to store the results of the whole computation at once. This is a good choice for the task at hand!
   It doesn't affect the point in (1.) though.
3. You seem to have already found the textbook algorithm.
4. There are various things to make the code prettier, but you'd have to do some testing to see if they make it work better.
   • Types are nice. They do nothing at runtime, but they let MyPy check for many kinds of mistakes.
   • I don't like the redundancy of path and seen, and I don't like that you're mutating seen the way you are, but I suspect the way you've written it is actually the most efficient for larger graphs.
   • The expression path + [src] makes two calls to the list constructor, and it's happening inside the for loop. That can be improved!
   • Since you never mutate a value of path, it can be a tuple instead of a list.
   • The way you have it set up now, your adjacencies dict will always contain src, so you don't need to use get.

I'm ignoring your outer wrapper, and I've made no effort to test this:

from typing import Iterable, Mapping, MutableSet, Sequence, TypeVar
N = TypeVar('N')
def dfs(source: N,  # The current node
        destination: N,  # The destination node
        path: Sequence[N],  # The path taken to the current node
        seen: MutableSet[N],  # The nodes visited on the path
        graph: Mapping[N, Iterable[N]]  # The graph being explored, as an adjacency dict
) -> Iterable[Sequence[N]]:
    new_path = (*path, source)
    if source == destination:
        yield new_path
    else:
        seen.add(source)
        for n in graph[source]:
            if n not in seen:
                yield from dfs(n, destination, new_path, seen, graph)
        seen.remove(source)