# Shortest path in a incomplete graph

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!

• Is the goal to find the shortest path, or just to get the robot to the goal? Are there physical constraints on the graph, or is it an arbitrary graph? Jun 12, 2019 at 19:08
• @BlueRaja-DannyPflughoeft The goal is to find shortest path to any of the exists. And, it's an arbitrary graph, the problem is that you cannot figure out the full graph but you only know the acceptable outgoing edges when you land on the node. The full graph size can be infinite, thus it's infeasible to compute every V and E ahead. Jun 12, 2019 at 21:58

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.