But then the code is not "pure" anymore and it even isn't different than the non-functional one.

My solution would be to make two changes. One to the fibbonacci heap and one to the graph that Dijkstra's is being used on.

I would have the pointers in the Dijkstra's graph be pointers to a mutable data structure (we do this to make sure there is only one place that we need to update per node in the fibbonacci heap and to localize our mutability and keep it out of the rest of our code).

I would then need to update the update code in the fibbonacci heap to take a general function which it will run on the nodes that are updated and which gets passed the original and updated nodes pointer. In the Dijkstra case you simply need to write a function which takes these pointers and has the mutable data structure and modifies it accordingly.

Thus you have kept your generality, confined your mutability and solved your problem at the expense of one pointer indirection and an added callback function (and the associated documentation).

This just proves that "pure" in this sense is a useless concept.

How so? All I'm seeing is that some speedups aren't possible. It still seems like a useful concept, particularly since "faster" was never one of its promises (maybe "easier to parallellize", though.).

Interestingly, in some cases it is actually faster. Modern hardware is peculiar in that respect.

But you can still provide a pure interface. If you implement Dijkstra in an imperative fashion, with lot's of mutations etc., as long as you don't have any external side effects (changing global variables or input variables) and return an immutable result, the function is pure for all practical purposes, even though it is implemented in an imperative fashion/style.