Suppose I am inside a finite, weighted cubic graph without loops, with no information regarding its layout, including the number of vertices or distances to the adjacent vertices. I want to reach a target vertex, but I will only know where it is once I reach it.
Assuming that the bottleneck on search time depends not on computation but only on the distance travelled within the graph itself whilst searching, what is the asymptotically fastest algorithm for reaching the target? My guess is that it'll still be a version of Dijkstra's for sparse graphs, modified to take into account the limited information available - but I have little intuition for this area and could be completely wrong.
Given this algorithm, what is a family of cubic graphs (ordered by number of vertices) on which the algorithm performs badly, in the sense that the ratio of mean square search time to mean square shortest path across all ordered pairs of vertices is high (when compared with other cubic graphs on the same number of vertices)?
Added for clarity, per the comments below:
- I can recognize a vertex once I've visited it, so that if I later return to it via a different path I will know where I am.
- If I am at one end of an edge that I have previously only seen the opposite end of, I can not recognize it.
- I will allow algorithms to turn around partway along an edge and return to the previous vertex in order to choose a different edge.