查找從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