## 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. |
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?
Wait. Wasn't this question already asked? And as I recall the answer was infinity...
Dave 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.
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
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
PS take this
http://www.codeguru.com/cpp/cpp/algorithms/article.php/c5119/ What is the size of your graph?
PS take this
http://www.codeguru.com/cpp/cpp/algorithms/article.php/c5119/ What is the size of your graph?.
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 |

Powered by FogBugz