**Problem Detail:**

I study Graphs Analysis by myself and i understood most of the material just fine. But, there is one huge problem with my approach that prevents me from solving tests. I don't know how to build new Graphs based on requirements and i'll give an examples:

Question: G = (V,E) is a directed graph with no cycles (DAG) and w: E->R for each edge. There is an efficient algorithm that in given vertices s and t in the graph it finds the minimum weight path contains with at least 3 edges. So far it great - i understand the question just fine.

Step 1: For each vertex v in V, we mark: v1 = (v, 1), v1 = (v, 2), v3 = (v, 3), v4 = (v, 4)

Given G = (V, E), we'll build new graph G'=(V',E') where: V'={v1, v2, v3, v4| for each v in V}

E' = {(v1, u2), (v2, u3), ____(1)____}

for each (ui, vj) in E', w(e) = {w(u, v)| (u, v) in E and (ui, vj) in E'}

(1) = ?

**a. (v3, u4), (v4, u4)** - the correct answer

b. (v3, u3)

c. (v3, u4),(v4, u3)

d. (v3, u4)

step 2: Apply DAG algorithm from s1.

step 3: return the weight of the path from s1 to t4.

I know how DAG works, but i don't know how to build the new graph in order to see it, how do i build the new graph?

i don't need to know what to do in every situation, i just don't know how to deal with it and build a new graph according the demands. The steps are derived from the question itself, but i didn't get the first step in the creation of the new graph. Why there is a need to create a new graph at all?

###### Asked By : Hanna

#### Answered By : JeD

Allright, if I read this correctly here is what I think it should do (Some parts are possibly missing or badly formatted, but the following should make sense):

You basically copy your graph 4 times into different *layers*. Let's call them L1,L2,L3,L4

In L1, the highest Layer, every connection from the original graph instead goes down to L2.

From L2 every connection goes to L3, and from L3 to L4

Finally L4 looks like your original graph.

So if you search for the shortest path between **u** and **v** with at least three edges, you start at **u in L1** and want to end at **v in L4**

Since you can only move down **1 layer at a time**, you need at least three edges to reach v.

Take this graph as an example:

Let's assume we want to move from the left to the right, and the upper connection is the

shortest one. Then the correct answer is still to move through every other node, because taking the shortcut uses too **few edges**.

If we convert this graph we obtain the following:

Here we want to reach the **bottom right** from the **top left**. As you can see, finding a solution in this graph, automatically gives us a solution with **at least three edges**.

Note: Sorry that the vertices are not labelled, could not figure out the text function in the drawing tool I used :/

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/60051

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback