Shortest path length when edge length is limited

89 Views Asked by At

$N$ nodes are uniformly distributed in a square whose side length is $1$. There exists an undirected edge between two nodes, if and only if the distance between them is less than or equal to $r$. Here we set a source $s$ and a destination $t$ in this square, and the distance between them is $d$. Now I want to find a shortest path from $s$ to $t$, that is, more precisely, the expectation of the path length from $s$ to $t$.
Note that $r=\Theta\left(\sqrt{\frac{\log N}{N}}\right)$, and it can ensure that the graph is connected.
$d$ might be a constant or a variable. Intuitively, the expectation of path length is $O(d)$.
I refer to many papers, Continuous Time Markov Chain is proposed to solve it. But they are aimed at the complete graph which does not apply to this case. Would you please provide me some idea to solve this problem ? Thank you!