Implement a graph in Python
find_path is very inefficient. Consider the following example, where we try to find a short path (just one edge) in a graph with just eleven nodes:

&gt;&gt;&gt; G = {i: list(range(10)) for i in range(10)}
&gt;&gt;&gt; G[0].append(10)
&gt;&gt;&gt; find_path(G, 0, 10)
[0, 10]


How long does this take?

&gt;&gt;&gt; from timeit import timeit
&gt;&gt;&gt; timeit(lambda:find_path(G, 0, 10), number=1)
1.3475657280068845


It really shouldn't take more than a second to find a path with a single edge in such a small graph. So why does it take so long?

The way that find_path works is that it generates all simple paths (paths with no repeated nodes) in depth-first order. However, in general there can be exponentially many simple paths in a graph. I constructed the graph G so that it looks like this:



The depth-first search starts by finding the path 0–1–2–3–4–5–6–7–8–9 but then it reaches a dead end:



So the search backtracks a couple of steps and then finds the path 0–1–2–3–4–5–6–7–9–8, but again it reaches a dead end:



You can see that the search will have to visit every path starting with 0 and visiting all of 1 to 9, before it will consider the path 0–10. But there are \$9! = 362,880\$ such paths.

To avoid this exponential runtime, you'll have to use a different approach, for example Dijkstra's algorithm.