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?
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.
Thanks in advance :) asked 02 Sep '15, 15:23

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
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
http://ideone.com/rU6vId  is there something wrong with my dfs? :)
(03 Sep '15, 01:30)
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)
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)
@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)

Why don't people just compute the longest distance via memoization in the recusion? i.e.
(code is in C++) Frankly, it seems so much easier to write and understand than a iteration over the topologicallysorted vertices. Well, that might be logical too, but still. answered 03 Sep '15, 14:07
