# Find all paths in a graph

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:

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

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)

• Is there any additional details needed? May 15, 2021 at 10:46

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:

• The other options would be to make a new set for the recursive seen, like you you're doing with path. Mutating values is often efficient, but opens up its own class of bugs. But as I understand it's somewhat expensive to spin up a new set instance (relative to other basic structures), so for this purpose your way is probably better. May 18, 2021 at 20:12
• I have one other question, assume a path exists like so '1 -> 2 -> 3 -> 4 -> 5 -> 6' and before that computation, I have already computed '2 -> 3 -> 4 -> 5', that was what I meant when I said how memoization can be used, as you can see, the second path is part of the result of the first path, can I not take advantage of this? I will clarify if you need more details May 19, 2021 at 1:01
• I understand what you mean by memoization, and I don't think it's going to help here. Suppose you've cached (memoized) the 2...5 path. Probably you've also cached all the other paths from 2. Great, but three problems: 1) You still have to iterate over all those 2... paths and output them; I don't think you can do that fundamentally faster than just rebuilding them all as-needed. 2) You have to store them all somewhere; that could be costly and/or slow. 3) You can't just iterate over all of them; any containing a 1 must be excluded, so there's still extra computation to do. May 19, 2021 at 2:13