Shortest path in a incomplete graph
Algorithms don't care whether you find out what edges lead from a vertex by looking them up in an array, by calling a function called get() or by waiting for divine revelation.

The only problem with Dijkstra's algorithm is that, as it is usually described, it starts by setting the distance estimate of every node to infinity and adding every node to a queue. You can't do that if you don't know the nodes at the start of the algorithm.  However, Dijkstra doesn't need to do this and, even if you do know the graph before you start, it's not very efficient.  It's enough to add the nodes to the queue as you discover them.  This variant of the algorithm is often called "uniform-cost search" (especially in AI), though some people argue that it's just Dijkstra's algorithm and that Dijkstra never really intended to add all the nodes to the queue at the start.

If you look at the two algorithms/versions of the algorithm, you'll see that a node that classical Dijkstra thinks is at distance infinity is a node that has not yet been added to the queue in uniform-cost.

Ariel Felner gave a good analysis of the relationship between classical Disjkstra and uniform-cost in Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Disjkstra's Algorithm (Proc. 4th Intl. Symposium on Combinatorial Search (SoCS 2011), AAAI Press, 2011; PDF).