CODEWITHSUNDEEP
phpalgorithmgraphlogic
recluze
recluze

Reputation: 1915

Find path from Point A to B with n number of Loops

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.

Upvotes: 0

Views: 251

Answers (1)

eisberg
eisberg

Reputation: 3771

Have a look at

  1. http://en.wikipedia.org/wiki/A-star
  2. Graph Algorithm To Find All Connections Between Two Arbitrary Vertices

Upvotes: 1

Related Questions