I'm looking for a way of naming the node of my graph such that knowing only the name of the node where I stand and the name of its direct neighbor, the name of the node I want to go and an algorithm I can find which node to hop to get closer to my destination node such that if I did this enough time I would effectively end up on the arrival node while crossing the least amount of node.
Here is an example that work well for a specific topology : I generate my graph by adding n node to the previously generated nodes and repeat the process as many times as we need. We end up with a fractal like graph. I would then name the central node 0. The first layer of node 0.0 - 0.n the second 0.0.0 - 0.n.n etc. I would then have to find the node that have the most matching digit with mine (with respect to their place) and if none is closer get one hop closer to the center. I am 0.3.4 and I want to go to 0.2.6. I would first choose 0.3, then 0 then 0.2 the 0.2.6
how could i generalize this to different topology like a small world network ? Or alternatively have a proof that it is not possible.
please excuse my clumsy way of describing the question.
In a general graph $G = (V,E)$, there's an obvious way of doing this : for each vertex $v$, precompute its distance to every other vertex, and store it in the "name" of the vertex (in graph theory we rather speak of labels but the idea is there). Then, when you want to find your path to a destination, compare your neighbourg's distance to it, and choose the best.
This is good, but it actually makes long names, and you have to precompute your distances, which is long (about $\Theta(|V||E|)$).
But unless you have better properties in your graph, there's probably nothing better to do. It's hard to prove though.