Let's imagine square-grid paper (or how you english men calls it) and two distinct nodes on it highlighted. Then there can be multiple paths of the same length linking the two nodes.

1) What are allowed operations for graph re-structuring?

2) Will resulting graph be still lattice after re-structuring? Or don't you demand preservation of that graph property - to be lattice?

Michal Trněný I have taken into account the questions you pointed out, preservation of the structure is not our priority given some features remain constant and certain operations are allowed, the challenge is to re-structure the graph so that for two distinct highlighted nodes on it, instead of multiple paths there exist only a single path. I havent' yet penned down the mathematics, but the resulting graph might not be lattice.

If the graph remains a lattice, the shortest paths between any two nodes should always be the same length.

Assume you start at (0,0) and you end at (x,y). Going along a lattice, where only 90 degree turns are allowed, the shortest path length is d = x + y, always.

First attempt. Just one leg along x, and one leg along y, and clearly, the total path length is x + y.

Or, you can cut the x direction in half, and the y in half, taking a zig-zag path. The path length becomes x/2 + y/2 + x/2 + y/2 = x + y.

In general, limit (as n -> ∞) of n * (x/n + y/n) = x + y.

Funny thing is, intuitively, you might expect that as n becomes very large, you should eventually get to the point where the path length becomes more like the hypotenuse of that triangle. But it does not, as long as 90 degree turns are mandatory.

Get rid of the mandatory 90 degree turns inherent with a grid, and the shortest path can, ultimately, be the hypotenuse of the triangle:

d = SQR(x2 + y2)

That's the shortest path, in Euclidean geometry. Must get rid of the lattice structure limitations entirely.