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 /> [![Grid_7x7][1]][1] <br /> <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/Uo2MN.jpg