0
$\begingroup$

I'm looking for some clarifications on an algorithmic task I've been trying to solve. This task is a part of Quiz 2 from the MIT 6.006 course.

The main idea of creating k-copies of a graph G is clear. What I'm really confused with is the final graph G':

  • Can you explain how the graph G' will look like?
  • How will the G' graph guarantee that all of the places {v0, v1, v2, vi} had been visited once we reached the destination vertex t?

I'm sorry if the community to post this question is wrong. Any suggestions are highly appreciated.

Input: enter image description here

Solution: enter image description here

Improve this question
$\endgroup$
0
$\begingroup$

Ok, I think here is how it should look like. You duplicate the graph G as many times as many v places you have to visit (e.g. v0, v1, v2). The order you must visit these vertices is the constraint which is expressed as zero weight edges (G1.v0 -> G2.v0, G2.v1 -> G3.v1).

enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.