Find all paths between two graph nodes

by

Finding all possible paths is a hard problem, since there are exponential number of simple paths. Even finding the kth shortest path [or longest path] are NP-Hard.

One possible solution to find all paths [or all paths up to a certain length] from s to t is BFS, without keeping a visited set, or for the weighted version – you might want to use uniform cost search

Note that also in every graph which has cycles [it is not a DAG] there might be infinite number of paths between s to t.

More Related Contents:

  1. What are the practical factors to consider when choosing between Depth-First Search (DFS) and Breadth-First Search (BFS)? [closed]
  2. Why is the time complexity of both DFS and BFS O( V + E )
  3. Why DFS and not BFS for finding cycle in graphs
  4. Best algorithm for detecting cycles in a directed graph [closed]
  5. Finding all cycles in a directed graph
  6. Graph Algorithm To Find All Connections Between Two Arbitrary Vertices
  7. Cycles in an Undirected Graph
  8. Breadth First Vs Depth First
  9. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  10. Find the shortest path in a graph which visits certain nodes
  11. Compute the minimal number of swaps to order a sequence
  12. Performing Breadth First Search recursively
  13. Find the paths between two given nodes?
  14. Finding all the shortest paths between two nodes in unweighted undirected graph
  15. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  16. Why is depth-first search claimed to be space efficient?
  17. Algorithm to simplify a weighted directed graph of debts
  18. Number of paths between two nodes in a DAG
  19. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  20. Finding connected components of adjacency matrix graph
  21. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1
  22. Is log(n!) = Θ(n·log(n))?
  23. What is the fastest integer factorization algorithm?
  24. Algorithm to list unique permutations of string with duplicate letters
  25. Collision detection of huge number of circles
  26. Find if a point is inside a convex hull for a set of points without computing the hull itself
  27. Myers diff algorithm vs Hunt–McIlroy algorithm
  28. Given Prime Number N, Compute the Next Prime?
  29. algorithm to check a connect four field
  30. What is the most efficient way to encode an arbitrary GUID into readable ASCII (33-127)?

Leave a Comment