0

I have a problem that I need guidance with. I have an array that has information about the edges between different nodes. So,

a[1][39] = 'p' --> Take transition 'p' while in node 1 to get to node 39. The complete graph is this: 

i[1][51] = 'p' 
i[1][39] = 't' 
i[39][40] = 'd' 
i[40][66] = 'p' 
i[66][51] = 'd' 
i[40][41] = 'm' 
i[41][64] = 'd' 
i[64][40] = 'd'

As you can see, it's a directed, cyclic graph. What I need to do is to have all paths from point X to Y. So, given X=1 and Y=51. I need output like so: 

o[0][0] = 'p'

o[1][0] = 't'
o[1][1] = 'd'
o[1][2] = 'p'
o[1][3] = 'd'

o[2][0] = 't'
o[2][1] = 'd'
o[2][2] = 'm'
o[2][3] = 'd'
o[2][4] = 'd'
o[2][5] = 'p'
o[2][6] = 'd'

The first index shows the path number. So, I have three paths here. The second index shows the step. So, one step in the first path, four in the second.

I'm doing this in PHP but even pseudo-code code would do. Also, I can also reverse the input array to i[1]['p'] = 51 etc. if that might help.

Thanks.

Dr. belisarius
  • 60,527
  • 15
  • 115
  • 190
recluze
  • 1,920
  • 4
  • 21
  • 34
  • Needless to say, this is a subset of the actual, much larger, graph. Also, I can live with cycles for now but will have to cap the loops to a specific number -- say, discard a path if it visits a node more than twice. – recluze Mar 31 '11 at 11:15

1 Answers1

1

Have a look at

  1. http://en.wikipedia.org/wiki/A-star
  2. Graph Algorithm To Find All Connections Between Two Arbitrary Vertices
Community
  • 1
  • 1
eisberg
  • 3,731
  • 2
  • 27
  • 38
  • How is that supposed to help? – rabbitisle Mar 31 '11 at 11:23
  • @eisberg I didn't ask the question. How is a heuristic algorithm which returns a single (best) path will help in returning all possible paths? What we need here is not a best answer but an enumeration of paths. – rabbitisle Mar 31 '11 at 11:31
  • 2
    @rabbitisle So you only need to change the terminating in A-Star and give your self an array of all solutions. – eisberg Mar 31 '11 at 11:33
  • @rabbitisle I am sorry I cannot rewrite the pseudo code at the moment. But you should be very careful when you collect all possible paths for lets say 20 points you can end up with million possibilities and looping for hours. – eisberg Mar 31 '11 at 11:46
  • Thanks for the tip. Q: If A* finds the shortest path, it wouldn't go through cycles, would it? I need paths with 'n' number of cycles. – recluze Mar 31 '11 at 11:53
  • @recluze A-Star is working with lists/stacks and can (without changes) only find one path without cycles. Maybe you can modify http://en.wikipedia.org/wiki/Dijkstra's_algorithm for that. – eisberg Mar 31 '11 at 11:56
  • Again, isn't Dijkstra only able to do shortest paths? I need all paths ... whether they're short or long. I'm not really concerned with distance here. Performance isn't really an issue either. – recluze Mar 31 '11 at 13:25
  • @recluze Something like http://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices ? – eisberg Mar 31 '11 at 13:26
  • That looks like a very comprehensive discussion. Thanks. – recluze Mar 31 '11 at 13:38