查找从A点到B点的路径（n个循环）

Question

我有一个问题，我需要指导。我有一个有关不同节点之间边缘信息的数组。所以，

a[1][39] = 'p' - >以过渡“P”，而在节点1到节点39.完全图是这样的：

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' 

正如你可以看到，这是一个直接，循环图。 我需要做的事是从点X到Y的所有路径。所以，给定X = 1和Y = 51。我需要这样的输出：

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' 

第一个索引显示路径号。所以，我在这里有三条路。第二个索引显示了该步骤。所以，第一条路是一步，第二条是四步。

我在PHP中这样做，但即使是伪代码也可以。另外，如果这可能有帮助，我也可以将输入数组反转为i[1]['p'] = 51等。

谢谢。

Answer 1

看一看

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