The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

finding all simple paths in an undirected graph?

I am looking for an algorithm which could find all simple paths in an undirected graph efficiently. My output would be all the paths with length.

The simplest way is just to enumerate all simple paths between each pair of vertices. But I am wondering is there any better solutions? Can I modify the matrix multiplication method for transitive closure to solve this problem?
Shenzhi Send private email
Friday, February 17, 2006
 
 
Wait. Wasn't this question already asked? And as I recall the answer was infinity...
Dave
Friday, February 17, 2006
 
 
I searched, but only found a topic about "finding all paths in a directed graph with cycles". As I am looking for simple paths, no cycles will be considered. So it will be finite, I believe.
Shenzhi Send private email
Friday, February 17, 2006
 
 
It is infinite, unless you add additional constraint, such as "we will only consider paths where a vertex is in the path at most N times".

For instance, here is an undirected graph comprised of two vertices and one edge:

A B
*-*

How many paths are there? Infinite...

AB
ABA
ABAB
ABABA
ABABAB

(Sadly, "ABBA" isn't one of them, dancing queen.)

Now, if you want algorithms in a DIRECTED graph, then I can help you out.
PWills Send private email
Friday, February 17, 2006
 
 
Doh! Didn't see that you were looking at simple paths until it was too late!
PWills Send private email
Friday, February 17, 2006
 
 
Can a simple path have more than two vertices in it?

If the answer is no, you can just use recursion (or the matrix formulas) if the nodes are defined and I think... permutation (without repetition) if they're not.

If the answer is yes, I think... combination (without repetition) will give you the total. I don't think there is a formula to instantly calculate the lengths of each possible leg when a leg consists of more than two nodes.
TheDavid
Friday, February 17, 2006
 
 
I think what you want is the A* algorithm.

http://en.wikipedia.org/wiki/A%2A
Kyle Send private email
Saturday, February 18, 2006
 
 
As far as I understand you are interested in so called "All-pairs shortest paths" problem since you have to find shortest paths to all pairs of vertices.
The problem is well-known both for unweighted and weighted graphs.
If you try this problem to solve in  straight way
for each vertex A in a graph G
  for each vertex B in a graph G\A
    find the shortest path from A to B (using Dijkstra's algorithm)
you need O(ne+n^2 log n) total time to compute all paths

Besided that you can use
Floyd algorithm which runs in O(n^3)
Dijkstra's algorithm run better on sparse graph, while Floyd's algorithm run better on dense graphs.
or johnson's algorithm which run in O(n e log n)
There exist fast probalistic algorithms to compute all shortest path
for example, Moffat-Takaoka algorithm which runs in O(n^2 log n)

I would recommend you to use Floyd algorithm if your graphs are not particularly large since it outperforms Dijkstra for reasonable size of the graphs
Andrei Lopatenko Send private email
Sunday, February 19, 2006
 
 
PS take this
http://www.codeguru.com/cpp/cpp/algorithms/article.php/c5119/

What is the size of your graph?
Andrei Lopatenko Send private email
Tuesday, February 21, 2006
 
 
PS take this
http://www.codeguru.com/cpp/cpp/algorithms/article.php/c5119/

What is the size of your graph?.
Andrei Lopatenko Send private email
Tuesday, February 21, 2006
 
 
As I understand, the initial problem was finding simple paths (not necessarily shortest paths). Thus a-b-c-d is a simple path even there is an edge between a and d.

I am quite interested in the answer to the original question as well. Any thoughts?
Zan Send private email
Sunday, March 05, 2006
 
 
I think your problem is NP-complete, since the problem of finding the longest simple path between 2 nodes is NP-complete...
DS
Friday, March 10, 2006
 
 
The only way to find the complete solution is to enumerate all permutations with 2, 3, ... N elements (N being the number of vertices in the graph), starting with S and ending with T (source and target node) and checking if each such permutation specifies a path in the graph.

kind regards,

D
DS
Friday, March 10, 2006
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz