Augment the grid graph $G$ on lattice points $[1,n]^2$, which
connects each point to its four distance-$1$ vertical and horizontal neighbors.
Augment $G$ to $G'$ by adding in one of the two $\sqrt{2}$ diagonals
to each $1 \times 1$ lattice square.
I am seeking to understand which selection of diagonal shortcuts will minimize the total length
of all shortest paths:
all shortest paths between the $\binom{n}{2}$ pairs of lattice points
in the augmented graph $G'$.
An example $G'$ is shown below.
<hr />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
[![enter image description here][1]][1]
<br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
<sup>
$n=7$.
</sup>
<hr />
Above the shortest path from $(1,1)$ to $(7,7)$ is $4+4\sqrt{2} \approx 9.7$,
while the shortest path from $(7,1)$ to $(1,7)$ is $6\sqrt{2} \approx 8.5$.

> ***Q***. What is the optimal choice of diagonals to minimize the sum of the lengths
of the shortest paths in $G'$  between all pairs of lattice points, for
arbitrary $n$?

Perhaps this has been studied before?
It seems related to [shortest-path trees](https://en.wikipedia.org/wiki/Shortest-path_tree),
but I am not seeing how that concept yields the optimal network in the described situation.

<hr />
Related: [Shortest grid-graph paths with random diagonal shortcuts](https://mathoverflow.net/q/45920/6094).


  [1]: https://i.sstatic.net/fFx88.jpg