In class we studied the Shortest-Path problem in a weighted graph. However, many

Question

In class we studied the Shortest-Path problem in a weighted graph. However, many problems in this assignment will involve the Longest-Path problem in a weighted, directed acyclic graph (DAG). In this problem, one is given a source s and a weighted DAG (G, w), and has to find the longest path from s to every node in the graph. Assuming that the weights in (G, w) are non-negative. The Longest-Path problem can be turned into the Shortest-Path version as follows: For each edge (u, v) in G, let w'(u, v) = -w(u, v). Thus finding longest paths in (G, w) becomes finding shortest path in (G, w'). However, the weighted graph (G, w') has negative weights, which we haven't studied. For the purpose of this assignment, we assume that there Is an algorithm LP(G, w, s) that associates each node v in G with a pair (n.dist, v.parent), where v.dist is the total weight on a longest path from s to v, and v.parent is the prior hop of v on this path. This algorithm takes O(n + m) time, where n is the number of nodes and m the number of edges in the graph. The Longest-Path problem can be solved by dynamic programming as follows. Let (G, w) be a weighted DAG whose weights are non-negative, and let s be a node in G. Assume that G has n nodes and m edges. Assume further that the node s has no incoming edges, meaning no arrow pointing at s if you draw the graph G.^1 First label the nodes of G by 0, 1, ..., n - 1 respectively such that for any edge (u, v), we must have label(u)

Explanation / Answer

2) a

If you try to get what the question want, you will find it quite similar to the topological sort. Topological sort arranges the vertices in the order such that each vertices children process first before its parent. In directed graph children is pointed by arrow head -> so for u->v edge, v is the children of u and when v will process all of its children then we will find u complete.

So suppose you have a graph like this

2->1

2->3

1->5

5->4

so what is the topological order for this.

So we will do basically a process each vertex sequentially and will number them their correct position.

so strart with 1, it has one outgoing edge so it will process that first so 5 will process,

after that 5 has one outgoing edge i.e. 5->4 so 4 will get process. Now 4 has no outgoing edge assign its value to be 1. As 5 has no other outgoing edge so assign 2 to it. Now 1 has no other outgoing edge so assign it 3.

So 4 will process first then 5 then 1. So if we label then 4 is labelled as 1, 5 as 2 and 1 as 3.

Then we will do for 2. 2 has two outgoing edges, one is 1 and another is 3. One has been processed so lets continue to its other adjacent vertex. 3 has not been processed so now process 3. 3 has no children so 3 will get assign number 4. Now 2 has no more children so 2 will get assign 5.

so correct label is 1->3, 2->5, 3->4, 4->1, 5->2

Now how to fild the longest path.

b)

Now we have our label. process sequentially in ascending order of label. It means first do for 4, then 5, then 1, then 3, then 2.

suppose these values are in array

label = [4, 5, 1, 3, 2]

Create a distance array A[] as asked

A[source] = 0; rest put big value basically very large here I take inifinity.

A will contain the answer. If you get any doubt you can ask me.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.