我需要一些帮助在 Mysql 和 Php 中实现最短路径问题。据我所知，BFS 算法是在无向和未加权图中找到这些路径的最佳方法。不过，我必须获得从一个顶点到另一个顶点的所有最短路径，这变得更加复杂。我已经为此找到了一个 Java 实现，但是对于我来说太复杂了，无法将它转录成 Sql。
因此，第一个问题是:我应该在哪里进行计算？ Mysql 还是 Php？哪里会更快？
另外，BFS 是最好的选择吗？有没有更容易实现的解决方案？如果没有，是否有人可以提供易于遵循和改编的代码供我引用？
谢谢!
最佳答案
将复杂的分层数据存储在像 MySQL 这样的平面关系数据库中并不简单，更不用说通过算法对其进行搜索了。我当然不建议尝试在 SQL 中实现用于搜索图形的算法。
就在 PHP 中实现广度优先搜索而言，有一些不错的选择 Tree implementations in PHP在 github 上可能会有帮助。 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 .
希望对您有所帮助。
关于php - mysql 和 php 中无向、未加权图中 2 个节点之间的所有最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33571476/