Jump to content
  • Advertisement
Sign in to follow this  
draconar

helping find and algorithm

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!