Suppose you have a network of edges connecting
each integer lattice point
in the 2D square grid $[0,n]^2$
to each of its (at most) four neighbors, {N,S,E,W}.
Within each of the $n^2$ unit cells of this grid,
select one of the two diagonals at random to
add to the network.
These diagonals serve as local "short cuts."
One could ask many questions about this model,
but let me start with this one:
> What is the expected length of the shortest path
in such a network from $(0,0)$ to $(n,n)$?
Here is an example for $n=25$:
<br />
![Shortest path between corners][1]
<br />
Here a shortest path has length
$10+20 \sqrt{2} \approx 38.3$
in comparison to the shortest possible length,
$25 \sqrt{2} \approx 35.4$.
For small $n$, the growth rate of the length of the shortest
path appears to be linear in $n$, with a slope of about
1.52315.
<br />
![Length vs. n][2]
<br />
I would appreciate learning if anyone recognizes
this model and/or knows the true growth rate. Thanks!
[1]: http://cs.smith.edu/~orourke/MathOverflow/RandShortCuts25.jpg
[2]: http://cs.smith.edu/~orourke/MathOverflow/RandShortCutsPlot.jpg