Take the 2-minute tour ×

I have to write an algorithm that find the path in DAG with single source and single sink... I really don't know what to do ( tried to use DSF and topological sort but nothing...) I don't want anyone to solve it for me but just some guidance.

Thank you

share|improve this question

1 Answer 1

up vote 0 down vote accepted

BFS finds shortest path in general unweighted graph - and also specifically in DAG [since it is also a graph]. It is also pretty simple to code it.

Note that DFS will find a path - but it doesn't have to be the shortest one.

You might also want to have a look at this post to see how to get the actual path from BFS after running it.

EDIT: according to your comments, it seems you want O(|V|) solution, and it doesn't have to be shortest. a modification of DFS is the way to do then, since the DAG has a single source and a single sink, every path from the source reaches the sink.

Note that since your graph is a DAG and since we established that every path from the source reaches the sink, you don't need to go backward after exploring a certain path [so no recursion or stack is needed].


  map <- new map
  current <- source
  while (current != target):
    next <- current.getNextVertex() //just chose an arbitrary edge and follow it, doesn't matter which
    map.put(next,current) //we "discovered" next by following current
    current <- next

after running this algorithm, you need to follow back the map from the target to the source - and you get the actual path [reversed of course]

The complexity is indeed O(n) because we visit each node at most once. In order to maintain O(n) the map has to be a hashmap [and not a treemap]. If the vertices are enumerated - you can even implement the map as an array.

share|improve this answer
I dont need to find the sourtest one.. just the one that will take O(n) –  Nusha Mar 25 '12 at 20:30
@Nusha: What is n? number of nodes in the graph? –  amit Mar 25 '12 at 20:30
number of vertices –  Nusha Mar 25 '12 at 20:31
@Nusha: DFS then gets you a O(n) solution in your case, I updated the answer with more details about it. –  amit Mar 25 '12 at 20:45
WOW!!! thank you soooo much! –  Nusha Mar 25 '12 at 20:47

Your Answer


