Earlier quoted context omitted.
None of these situations require an object to do. You can always have a function that takes in an extra ‘state’ argument. You can then do everything you said by passing in the corresponding state values.
Precisely. And that's the way it's done in functional languages.
In a FPL your graph will be an ADT. The advantage is clients can pick it apart, but there is no easy way to extend it. If you wanted to "use the same object for computing distances to multiple vertices", you're screwed: the ADT is laid bare, and there is no data hiding.
In an OO language, your graph will be an opaque object, and you can write things like CachingDijkstra or ParallelDijkstra and make these work transparently for your clients. The price is that you are bound to your APIs: a client cannot pick apart your data structure, because it's opaque.