1
$\begingroup$

I have many questions which related to this topic. I saw somewhere that a topological sorting can be used to find shortest path, and in DAG it can even find shortest weighted paths of all vertex by asking about each vertex whether it's weighted higher than edge plus previous vertex. The point is, I don't understand since we are in DAG why isn't DFS alone enough to find shortest paths. Both weighted and unweighted. I also don't understand why we need a stack in topological sort. If you were to perform a DFS on some DAG. It will automatically produce a topological sort, if you do a pre-order DFS traverse.

$\endgroup$
  • $\begingroup$ For your last part are you saying about performing preorder traversal of resulting dfs-tree? Or is it something else? $\endgroup$ – Vimal Patel Nov 2 '19 at 9:59
  • $\begingroup$ No. Doing a regular pre-order DFS. But on each vertex u would ask the same question we ask in topological sort $\endgroup$ – bilanush Nov 2 '19 at 12:32
  • $\begingroup$ cs.stackexchange.com/q/4914/755 $\endgroup$ – D.W. Nov 3 '19 at 7:32
1
$\begingroup$

The only question is in the tile so I'm going to answer that.

A DFS visit from a source $s$ of a unweighted DAG $G$ does not find the shortest paths of $G$ from $s$. As a counter example look at the following graph: counterexample

If vertex $a$ is visited before vertex $b$ you will not necessarily discover the shortest path from $s$ to $b$.

Also, the same example shows that the order in which vertices are considered by a preorder DFS traversal is not necessarily a topological sort. Indeed, if $b$ is visited before $a$ the order would be: $s, b, a$ but there is an edge from $a$ to $b$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ok, ur example works only because u can still create a fake circle because it's a directed graph. What about an undirected graph, would my question then be valid? $\endgroup$ – bilanush Nov 2 '19 at 12:03
  • $\begingroup$ No. Consider the undirected version of the above graph. If $a$ is visited first by a visit from $s$, then $b$ will be discovered though the path $s - a - b$ of length $2$. If $b$ is visited first, then $a$ will be discovered though the path $s - b - a$. $\endgroup$ – Steven Nov 2 '19 at 13:08
  • $\begingroup$ Nooooooo of course I am talking about an acyclic graph. For sure. Other wise of course there is no difference between this to what u wrote $\endgroup$ – bilanush Nov 2 '19 at 13:49
  • 1
    $\begingroup$ If the graph is undirected and acyclic then it is a forest. A DFS from $s$ on a tree will clearly find the (unique) shortest path from $s$ to any other vertex of the tree. $\endgroup$ – Steven Nov 2 '19 at 13:56
1
$\begingroup$
  1. Why don't we just use DFS to find shortest path in DAG?

For this try to find shortest path from source vertex $0$ to all vertex in following graph.

graph_example

In particular if DFS visits $1$ first from $0$ then it will assign shortest path distance $10$ to $4$ which is wrong.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Your example DAG is not unweighted. However the counterexample still works in its unweighted version: if $1$ is visited first, the distance from $0$ to $4$ will be $2$; if $2$ is visited first, the distance from $0$ to $4$ will be $4$. $\endgroup$ – Steven Nov 2 '19 at 10:35
  • $\begingroup$ In question itself it is mentioned that proposed method to finding shortest path would work for both weighted and unweighted directed acyclic graphs. Hence I think my counterexample would be valid. $\endgroup$ – Vimal Patel Nov 2 '19 at 10:38
  • $\begingroup$ No, main question asked about unweighted. About weighted of course I meant to ask to replace topological sort with stack. By doing DFS but by asking on each vertex what we would ask with a topological sort. Meaning, let's do a DFS and when we encountere later vertex 1 from vertex 3 we would ask if our route is cheaper from here and we would update vertex 1 to cost 4 $\endgroup$ – bilanush Nov 2 '19 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.