Some doubts in longest walk in graph

general
, ,
1

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 :slight_smile:

2

  1. Because it is dynamic programming, and like in every dinamic programming problem, you have to proceed vertices in sorted order. Answer for some vertex X depends only on answers to vertices which are on the one side from it in your topsort order, and you need these answers to calculate correct one for vertex X.

  2. What about graph having more than one vertex without incoming edges? If your question is about vertex s only, like it is in that article - yes, you can limit yourself to vertices which are reachable from S only; however, for longest walk in general you’ll need all graph.

  3. Yes, it can. Your logic is correct.

  4. Yes, it is faster. Complexity is mentioned at the end of that article, and you can compare it with Dijkstra’s complexity:) Using Dijkstra for this kind of graphs sounds stupid :slight_smile:

1 Like
3

thank you.

4

I still have problem with the first one. If we do not use topological sorting, rather use a simple dfs, we would still be getting the answer, won’t we? Simply setting the answer to each vertex to -INF and using the given algorithm will yield the same result in same time as dfs, I think

5

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.

6

What is the difference between dfs ans “topological sorting” here? DFS itself is producing topological sorting :slight_smile: So you may not store that sorting itself, if you want - but that doesn’t change things.

7

Here we need the reversed of postorder dfs as order. I don’t see the dfs recursion to process in this order directly.

8

http://ideone.com/rU6vId - is there something wrong with my dfs? :slight_smile:

9

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.

10

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 :slight_smile:

11

@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.

12

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.