在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。

希望有所帮助。