View Single Post
Old 06-12-2018, 01:08 PM
uigrad's Avatar
uigrad uigrad is offline
Senior Member
Join Date: Jan 2014
Posts: 114

I agree with both people above me. The solution given is minimal.

The logic that fiddleback explained is the same as the logic that Euler used to prove that the Seven Bridge problem had no answer:

Since there are 2 vertices with odd numbers of paths, we know that the shortest solution will have at least 2 repeated paths. The shortest paths are 150m, so we know that the shortest minimum amount of extra walking will be 300m.

The solution by charlieabranches contains only 300m of extra walking. So, we can conclude that it is minimal.

Sometimes I've seen questions like this with a part 2, which to make a path that is minimal that doesn't cross itself. An example that is minimal that doesn't cross itself is here:

Last edited by uigrad; 06-12-2018 at 01:18 PM.
Reply With Quote