Number of paths between two nodes in a DAG

by

Do a topological sort of the DAG, then scan the vertices from the target backwards to the source. For each vertex v, keep a count of the number of paths from v to the target. When you get to the source, the value of that count is the answer. That is O(V+E).

More Related Contents:

  1. Best algorithm for detecting cycles in a directed graph [closed]
  2. Finding all cycles in a directed graph
  3. Graph Algorithm To Find All Connections Between Two Arbitrary Vertices
  4. Find all paths between two graph nodes
  5. Cycles in an Undirected Graph
  6. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  7. Find the shortest path in a graph which visits certain nodes
  8. Compute the minimal number of swaps to order a sequence
  9. Find the paths between two given nodes?
  10. What are the practical factors to consider when choosing between Depth-First Search (DFS) and Breadth-First Search (BFS)? [closed]
  11. Why is the time complexity of both DFS and BFS O( V + E )
  12. Why DFS and not BFS for finding cycle in graphs
  13. Algorithm to simplify a weighted directed graph of debts
  14. Finding connected components of adjacency matrix graph
  15. O(n) or O(n)^2 time complexity of the algorithm? [closed]
  16. How can I find the time complexity of an algorithm?
  17. Peak signal detection in realtime timeseries data
  18. How to compare two colors for similarity/difference
  19. Least common multiple for 3 or more numbers
  20. Negative weights using Dijkstra’s Algorithm
  21. What’s the fastest algorithm for sorting a linked list?
  22. Need help in mod 1000000007 questions
  23. SICP example: Counting change, cannot understand
  24. Algorithm to tell if two arrays have identical members
  25. Quicksort vs heapsort
  26. Algorithm to find the most common substrings in a string
  27. Simplest way to get the top n elements of a Scala Iterable
  28. Find cycle of shortest length in a directed graph with positive weights
  29. How is 2D bin packing achieved programmatically?
  30. Optimizing Conway’s ‘Game of Life’

Leave a Comment