×

# Some doubts in longest walk in graph

 0 I was going through this link and I have some doubts. 1) Why is topological sorting used here? What will be the problem if we don't use it? 2) In function longestPath(), topological sort is used on all vertices. Why is that?  for (int i = 0; i < V; i++) if (visited[i] == false) topologicalSortUtil(i, visited, Stack);  For the graph given in the site, calling it once for the source works too.  topologicalSortUtil(s, visited, Stack);  3)Can this be used for finding shortest path in the graph too? I think it should be possible if we swap the less than sign to greater than sign. 4)If it can be used to find shortest path, then is it faster or dijkstras? Thanks in advance :) asked 02 Sep '15, 15:23 893●2●11●35 accept rate: 10%

 0 Concerning the order in which you search: If you're missing out one node, the result of the next node will be ultimately correct, but the result for the node after that will in general not. Consider a DAG with 4 nodes 1..4, source 1 and edges 1->2 2->3 1->4 4->2  and edge weight constant 1. A possible dfs order is 1,2,3,4. This yields a path length of 2 for 1->3, since 3 is not updated again after the path length to 2 is updated to 2. answered 02 Sep '15, 21:51 7★ceilks 1.8k●9 accept rate: 36% http://ideone.com/rU6vId - is there something wrong with my dfs? :) (03 Sep '15, 01:30) lebron7★ No, but it's a different problem from the one given n the link. You compute the maximal length of a path starting any node in the subDAG starting at the source. The problem from the link computes all maximal paths from the source to any of those node. For the source both are obviously identical. The first problem transports information from the leafs and is directly solvable by dfs postorder as you've shown. I still don't see how the other, transporting information from source to leafs can be implemented only using dfs order. (03 Sep '15, 03:15) ceilks7★ Oh, sorry then; yep, you are right - for a different problem you are talking about, it actually doesn't sound as a dfs - we have some sort of reversed problem here :) (03 Sep '15, 03:43) lebron7★ @ceilks Can you say this part again "since 3 is not updated again after the path length to 2 is updated to 2."? I didn't get this. (03 Sep '15, 10:15)
 0 Why don't people just compute the longest distance via memoization in the recusion? i.e. int getDist(int node) { if(Comp[node]) return Dist[node]; Dist[node] = 0; for(auto e : Adj[node]) { Dist[node] = max(Dist[node], getDist(e.neighbor) + e.cost); } Comp[node] = true; return Dist[node]; }  (code is in C++) Frankly, it seems so much easier to write and understand than a iteration over the topologically-sorted vertices. Well, that might be logical too, but still. answered 03 Sep '15, 14:07 150●3 accept rate: 12%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,236
×28
×4

question asked: 02 Sep '15, 15:23

question was seen: 928 times

last updated: 03 Sep '15, 14:09