php - 地图中的最短路径

Question

我在 mysql 中使用规范化邻接列表设计了一个加权图。现在我需要找到两个给定节点之间的最短路径。

我曾尝试在 php 中使用 Dijkstra，但我无法实现它（对我来说太难了）。我觉得另一个问题是，如果我使用 Dijkstra，我需要考虑所有节点，这在大图中可能效率很低。那么有人有与上述问题相关的代码吗？如果有人至少向我展示了解决这个问题的方法，那就太好了。我已经被困在这里将近一个星期了。请帮忙。

Answer 1

这听起来像是 A* 算法的经典案例，但如果你不能实现 Dijkstra，我就看不到你实现 A*。

维基百科上的 A*

编辑：这假设你有一个很好的方法来估计（但你不要高估）从一个节点到目标的成本。

edit2：您在使用邻接表表示时遇到问题。我突然想到，如果您为地图中的每个顶点创建一个对象，那么当有链接时，您可以直接链接到这些对象。所以你所拥有的本质上是一个对象列表，每个对象都包含一个指向它们相邻节点的指针列表（或引用，如果你愿意的话）。现在，如果您想访问新节点的路径，只需点击链接即可。请务必维护给定顶点所遵循的路径列表，以避免无限循环。

至于每次您需要访问某些内容时查询数据库，无论如何您都需要这样做。您最大的希望是仅在需要时才查询数据库...这意味着仅在您想要获取图中特定边的信息或图形中一个顶点的所有边时才查询它（后者可能是更好的路线），所以你只偶尔打一次慢速 I/O，而不是一次全部打大块。

Answer 2

这是 Java 中 Dijkstra 算法的文字版本，它可以帮助您弄清楚如何在 PHP 中实现它。

http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29

Answer 3

Dijkstra 算法返回从给定顶点到其他顶点的最短路径。你可以在Wiki
中找到它的伪代码。

但我认为您需要Floyd算法来找到 DIRECTED 图中所有顶点之间的最短路径。

两者的数学复杂性非常接近。

我可以从 Wiki 中找到它们的PHP 实现。