Reminds me of a university project I did 6 years ago: we had to compute a bunch of shortest paths in a large graph, during the computation of reach [^1]. There were a small number of sources but a large number of queries, that were not easily predictible in advance.

The assignment was quite computation intensive and advised to use C++ or Java.

I had a tradeoff to make on each source between computing a full Dijkstra's (distance to all other nodes) or multiple "lazy" Dijkstra's (stopping upon reaching the target node).

Instead, I had a nice idea: what if I could continue computations at the last known Dijkstra's state?

To implement it, I could either: - create an object, list all variables of my Dijkstra's and put them in a dict state - use an iterator that looks very much like the textbook Dijkstras's and use the `next()` Python method to pass queries, while the state variables AND the instruction pointer are stored in the closure

This is a really good illustration that `next` makes closures "mutable" and "callable" as the link states.

The resulting code of an "AWESOME ONLINE MEMOISED DIJKSTRA" as I wrote in the docstring back then is stupidly small and simple to read [^2]. It is also easy to call: `dijkstra_with_target(graph, source).send(target)`.

In the end, my Python code (executed with Pypy) outperformed all C++ and Java implementations by an order of magnitude.

I should write a blog post about this (and almost did here)!

[^1]: https://www.irif.fr/~kosowski/INF421-2016/problem.html

[^2]: https://github.com/louisabraham/INF421-project/blob/master/s...