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.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ For your last part are you saying about performing preorder traversal of resulting dfs-tree? Or is it something else? $\endgroup$– Vimal PatelNov 2, 2019 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$– bilanushNov 2, 2019 at 12:32
-
$\begingroup$ cs.stackexchange.com/q/4914/755 $\endgroup$– D.W. ♦Nov 3, 2019 at 7:32
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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:
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$.
-
$\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$– bilanushNov 2, 2019 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$– StevenNov 2, 2019 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$– bilanushNov 2, 2019 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$– StevenNov 2, 2019 at 13:56
$\begingroup$
$\endgroup$
3
- 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.
In particular if DFS visits $1$ first from $0$ then it will assign shortest path distance $10$ to $4$ which is wrong.
-
$\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$– StevenNov 2, 2019 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$ Nov 2, 2019 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$– bilanushNov 2, 2019 at 12:12