Find all paths between two graph nodes

algorithm graph-theory graph-algorithm breadth-first-search
Paul picture Paul · Mar 2, 2012 · Viewed 150.4k times · Source

I am working on an implemtation of Dijkstras Algorithm to retrieve the shortest path between interconnected nodes on a network of routes. I have the implentation working. It returns all the shortest paths to all the nodes when I pass the start node into the algorithm.

My Question: How does one go about retrieving all possible paths from Node A to say Node G or even all possible paths from Node A and back to Node A

Answer

amit picture amit · Mar 2, 2012

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.

Related questions

When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)?

I understand the differences between DFS and BFS, but I'm interested to know when it's more practical to use one over the other? Could anyone give any examples of how DFS would trump BFS and vice versa?

Read More
Finding all cycles in a directed graph

How can I find (iterate over) ALL the cycles in a directed graph from/to a given node? For example, I want something like this: A->B->A A->B->C->A but not: B-&…

Read More
Relaxation of an edge in Dijkstra's algorithm

What does relaxation of an edge mean in the context of graph theory ? I came across this while studying up on Dijkstra's algorithm for single source shortest path.

Read More