php - map 中的最短路径

Question

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

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

Answer 1

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

A* on Wikipedia

编辑:这假设您有一个很好的方法来估计(但重要的是您不要高估)从一个节点到目标的成本。

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

就每次需要访问某些内容时查询数据库而言，无论如何您都需要这样做。你最好的希望是只在你需要的时候查询数据库......这意味着只在你想要获取图中特定边的信息时查询它，或者只查询图中一个顶点的所有边(后者可能会是更好的路线)所以你只是偶尔遇到一次缓慢的 I/O 而不是一次巨大的 block 。