0

Given a directed acyclic graph, how can I find the number of paths from vertex u to vertex v in using a dynamic programming algorithm that runs in linear time(if possible, through also using topological sorting)?

Leran Dagash
  • 65
  • 7
  • Found an answer for the question here: https://stackoverflow.com/questions/18087559/topological-sort-to-find-the-number-of-paths-to-t?rq=1 – Leran Dagash Jan 04 '21 at 16:47
  • Does this answer your question? [Topological sort to find the number of paths to t](https://stackoverflow.com/questions/18087559/topological-sort-to-find-the-number-of-paths-to-t) – גלעד ברקן Jan 04 '21 at 19:02
  • Check this link [All_Paths_In_A_DAG](https://www.algotree.org/algorithms/tree_graph_traversal/depth_first_search/all_paths_in_a_graph/) The method described in this link uses a simple DFS with backtracking to find all paths in a directed acyclic graph. – ktime Jan 10 '21 at 21:27

0 Answers0