Finding any path between nodes of implicit, finite, regular, undirected graph Consider a 4-regular, finite, non-directed, integer-weighed graph $G$. Let each node carry an integer value indicating its distance from zero on a hypothetical axis $X$. Take a given node $N$ for which we know its distance from zero (either negative or positive) and the weights on the edges incident to it. Note, that for each node, two of the edge weights are positive and two are negative. All four are integers.  Let $N_0$ denote the node with distance zero on the $X$-axis. In the graph there is at least one $N_0$. 

To better illustrate it see an outline diagram (apologies to readers with impaired eyesight for not including high contrast image).

 

Central blue node in the example has some negative distance from zero (black axis). Now, this node (like each node in this graph) has four edges with weights: w1 and w2 are positive-valued (so that if you choose to move along w1 and w2 this will bring you closer to zero on the axis), while w3 and w4 are negative. In the picture the blue node is connected with the target node with distance zero, but this is of course just for illustration. 

Although the graph is finite, it is very large ($&gt;10^{500}$ nodes or so), so one cannot represent the entire graph at once in RAM. 

Take any initial node $N$ with weights $w_1,w_2,w_3,w_4$ and distance $d$. If one traverse along either of the four edges towards neighbour node, then all remaining weights in this neighbour can be easily calculated based on the weighs of the initial node (they form some arithmetic sequences, formulae of which are given). 

Problem: Find any path (not necessarily the shortest) from $N$ to $N_0$ for the graph described above. The algorithm should basically provide values of subsequent edges (with their weighs) constituting the relevant path to $N_0$. What is the expected computational time complexity?

Additional - strictly related to the problem: Does one need to map the entire graph into memory in order to launch any suitable search algorithm?
The distances of your nodes and the weights of the edges can be used as a heuristic for an algorithm like $A^*$. That might be reasonably efficient in practice, but in the worst case still looks at the whole graph.

Another possibility is using a random walk with a bias for edges that take it closer to the goal. Then you need memory proportional to length of the path you discover (you can prune cycles to improve this in practice).

If you want to minimize memory consumption (while probably exploding your runtime) you can use the logspace algorithm for graph connectivity.

As you say that your graph is bigger than what can be stored on a universe-sized computer, I assume that you have some efficient representation. Should the input to your algorithm be reasonably big as well, you should be careful to use an IO-optimized algorithm. This blog post might serve as a start.