在mysql和php中的無向，未加權圖形中的2個節點之間的所有最短路徑

Question

我需要一些幫助來實現Mysql和Php中的最短路徑問題。據我所知，BFS算法是在無向圖和未加權圖中找到這些路徑的最佳方法。不過，我必須從頂點到另一個得到所有最短路徑，這會變得更加複雜。我爲此找到了一個Java實現，但對於我將其轉錄到Sql中來說太複雜了。

所以，第一個問題是：我應該在哪裏做計算？ Mysql或Php？哪裏會更快？

另外，BFS是最好的選擇嗎？有沒有更容易實施的解決方案？如果沒有，是否有人可以很容易地遵循和適應代碼，我可以用作參考？

謝謝！

Answer 1

在像MySQL這樣的平面關係數據庫中存儲複雜的分層數據並不是小事，更不用說算法搜索它了。我當然不會推薦嘗試在SQL中搜索圖表的算法。

就PHP實現廣度優先搜索而言，在github上有一些好的Tree implementations in PHP可能有幫助。 A good article for reference on dealing with btrees in PHP - 特定於PHP。沒有足夠的權重來加權，無向圖，但通用性足以提供一些方向。廣度優先搜索基本上只是一個隊列/堆棧，您可以將葉節點從分支中彈出，因此迭代或遞歸實現並不困難。

做的最短路徑搜索最簡單的方式，在我看來，是A* search，即使它不能保證找到所有最短路徑，如BFS，因爲它通常只要它的發現結束節點停止，它可以更容易實現，而不是無法調整搜索所有路徑。

還有Dijkstra的算法，它和A *都很適合找到最短路徑。這是一個很好的cs.stackexchange answer I found on contrast between Dijktra and BFS for shortest path。

希望有所幫助。