Shortest path in a incomplete graph

Question

I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. Retrieving the shortest path of a dynamic graph

My question is a little different.

Given the entry node $S$, while the entire graph $G(V, E)$ is unknown at the beginning. There's a function public List<Edge> get(Node node) to figure out the outgoing weighted edges at each node. Also, there's another function public boolean isExit(Node node) tells you when to stop if the node is an exit node.

The question is a lot like the shortest path finding problem in a maze, where you're at the entry, you only know the next moves of the current node and past nodes, you'd like to find the exits (multiple) in the shortest path. In this analogy, we care more about how to find the "exit" quickly, rather than finding the global optimal shortest path.

I'm wondering if the normal Dijkstra algorithm (Greedy + Relaxation) still applies in the case.

Because we don't know the full graph, the shortest path to a node might haven't been explored yet, and exist in the unknown part. (That's my biggest concern).

I hope my explanations are clear enough, thank you very much!

Answer 1

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).