# helping find and algorithm

This topic is 2778 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi guys!,

My problemo is:
I need to find ALL possible paths within a bi-directional graph from a given edge (by bi-directional I mean that every vertice of the graph is conected to the last edge in a 2 way direction).

For example, my adjacency matrix is

0 | 1, 2, 3, 5
1 | 0, 2, 3, 5
2 | 0, 1, 3

and so on.

I want my alg to start at point 0 and find all possible paths that I can take from zero. I've tried to use a depth-first alg, but it bails out as soon I reach the "longest" branch. But what I need is the alg to backtrack to the longest branch - 1 and find any other possible path from there.

A simple backtracking alg would to the trick? if yes, which one?

many thanks!

##### Share on other sites

I need to find ALL possible paths within a bi-directional graph from a given edge (by bi-directional I mean that every vertice of the graph is conected to the last edge in a 2 way direction).

There are infinitely many.

Unless you decide how to handle cycles.

Take a simple graph of 3 nodes, all connected to each other. Path from 1 to 3 is:
1-2-3
1-2-1-3
1-2-1-2-3
1-2-1-2-1-3
1-2-1-2-1-2-3
....

##### Share on other sites

[quote name='draconar' timestamp='1305209820' post='4809789']
I need to find ALL possible paths within a bi-directional graph from a given edge (by bi-directional I mean that every vertice of the graph is conected to the last edge in a 2 way direction).

There are infinitely many.

Unless you decide how to handle cycles.

Take a simple graph of 3 nodes, all connected to each other. Path from 1 to 3 is:
1-2-3
1-2-1-3
1-2-1-2-3
1-2-1-2-1-3
1-2-1-2-1-2-3
....
[/quote]

hi! I don't want to circles. If a edge was visited within one branch, I don't want to visit it anymore. e.g.:

1-2-3 - OK
1-2-1-3 - NOK, 1 is visited already
1-2-1-2-3 - NOK, 1 & 2 visited

but I do want to find:
1-2-3
1-2
1-3
1-3-2

etc...

1. 1
2. 2
Rutin
19
3. 3
khawk
18
4. 4
5. 5
A4L
11

• 12
• 16
• 26
• 10
• 44
• ### Forum Statistics

• Total Topics
633767
• Total Posts
3013739
×