-1

I'm wondering if there's actually an easy technique (other than trial & error) to find the shortest path (which covers all paths).

I googled and discovered that all paths in this diagram cannot be passed only exactly once based on the Euler Theory (correct me if I'm wrong). I am a first-year maths student so I haven't studied graph theory yet!

Still hoping that I can get some insights on some techniques on solving this enter image description here
as I doubt that the minimum value I got is accurate.

Thanks in advance!

Ross Millikan
  • 374,822
user672518
  • 97
  • 1
    What do you mean by "the shortest path which covers all paths?" There are algorithms to find the shortest path from the entrance to the exit. What does the bit about covering all paths mean? – saulspatz May 09 '19 at 14:30
  • 1
    Does each edge in the graph have a length, or are you just asking the fewest number of edges one must traverse, some of them more than once, to cover all the edges of the graph? – Ross Millikan May 09 '19 at 14:45
  • Please answer the questions in the previous comments. Meanwhile I vote to close the question. – callculus42 May 09 '19 at 15:47
  • Sorry for the misunderstanding. The lines in the diagram represents paths, the numbers on the diagram indicates the length of the paths, whereas I need to find the shortest path which will pass through all paths starting from the entrance – user672518 May 10 '19 at 01:03

1 Answers1

2

A first step is to count the number of odd vertices. As you have seen, you can make a Eulerean path in those graphs with two odd vertices and a Eulerean cycle in those graphs with none. If there are two, the path must start at one odd vertex and end at another. In your example there are four odd vertices: $B,D,F,H$. Given the entry and exit constraint, you need to duplicate a path from $B$ to $H$, so pretend there is one more link. The shortest path from $B$ to $H$ has length $300$ so that will be your added length. Now that you have added this path, you have only two odd vertices and are asked to start at one and end at the other, so the minimum length will be the total of all the paths plus $300$.

Ross Millikan
  • 374,822
  • Thank you for the reply, it really cleared my doubts. But I'm just wondering, since this is a puzzle, what if I assume that we need to start at the entrance but need not end at the exit to complete all paths? – user672518 May 10 '19 at 01:05
  • If that's the case, since there are 4 odd vertices in this diagram, is it also necessary for the path to start at one of the odd vertices and end at another in order for the paths to be the shortest covering all routes? – user672518 May 10 '19 at 01:16
  • Without repeating edges you have to have one path per two odd vertices. You have to connect those paths into one by repeating edges. In this case there are four odd vertices so (if there is no entry and exit restriction) you can repeat paths to connect any pair, then start at one of the remaining ones and finish at the other. The shortest path will come from the shortest connection between any two odd vertices. – Ross Millikan May 10 '19 at 01:46