Cubic graphs which are "difficult to navigate" 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.

 A: Since you used the word "travelled", I am guessing you want a traversal-based type of algorithm.  If you have other means of searching the graph, you should make it clear.
This really sounds to me like a cow-path problem.  However, you might try search games to see if other algorithms like those for the Chinese postman problem are more suitable for your problem.  If you do a web search on cow-path, you will find a randomized algorithm where the expected runtime is (a real number which is) about 7 times the distance from the goal.
Gerhard "Ask Me About System Design" Paseman, 2011.07.27
A: With respect to your question about on which graphs the algorithms performs poorly, have you considered expanders?  Expanders look locally tree-like, which means that the number of vertices at distance $d$ from your starting vertex is exponential in $d$ (at least as long as the ball of radius $d$ around the start vertex has less than half the graph).  Thus, even if your algorithm visits vertices in an ideal order, it should take exponentially longer than following the shortest path.  
