CODEWITHSUNDEEP
javaalgorithmgraphcomputer-science
newToJava
newToJava

Reputation: 31

Find the possible shortest path between two vertices

So let's say I have a graph like this, I can only visit 6 vertices at a time, for example, I can visit maybe 123654 for the first time and when I move again I need to start at the end vertex I visited last time so for the example given I have to start at 4, then I can do 432567. The goal is to start from 1 and end at exactly 7 for my last element of any moves.

Is there any way to achieve this? I have been stuck on this problem for weeks now, so far my idea is to keep exploring all the possible routes I may find but I don't think it is a correct algorithm, is there a better idea? enter image description here

Upvotes: 0

Views: 144

Answers (1)

default locale
default locale

Reputation: 13446

Step 1. Find all the paths of the length 6 from vertex 1 (V1). You can use DFS for that:

123456
123654
125436
125634

I assume, that you can't visit the same vertex twice in the same "run". If you can you'll get a bigger list.

Step 2. Find all the paths of the length 6 from V7:

765432
765234
763452
763254

Step 3. Find a vertex you can reach in a single run from both V1 and V7

It's vertex number 4. Then you can construct two runs that let you go from V1 to V7:

123654
432567

Step 4. You can generalize this algorithm to an arbitrary graph.

  1. Using DFS or BFS build a list of vertices reachable from V1.
  2. Repeat this step for every vertex reachable from V1 until you reach V7 (or V[Last]).

What you need is to run a short DFS (6-vertex "runs") within a long DFS (vertices reachable after each run).

Upvotes: 2

Related Questions