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

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 https://www.irif.fr/~kosowski/INF421-2016/problem.html [^2]: https://github.com/louisabraham/INF421-project/blob/master/src/Dijkstra.py#L53 https://github.com/louisabraham/INF421-project/blob/master/s...