地图中的最短路径

Question

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

我尝试在php中使用Dijkstra算法，但我无法实现它（对我来说太难了）。另一个问题是，如果我使用Dijkstra算法，我需要考虑所有的节点，在大型图中可能非常低效。所以，有没有人有与上述问题相关的代码？如果有人能向我展示解决这个问题的方法，那就太好了。我已经被卡在这里将近一周了。请帮帮我。

- 5lackp1x3l0x17

---

你有什么建议？我两个都可以，但是内存更可取。 - 5lackp1x3l0x17

你究竟在哪个地方卡住了呢？同时，你说得对，对于大数据集来说，Dijkstra算法的确会显得比较慢。 - San Jacinto

我可以实现Dijkstra算法，如果给定了加权邻接矩阵，但是当涉及到邻接表时，我会遇到困难。另一个方面是，如果每次都要使用Dijkstra来查找最短路径，我将不得不通过php在mysql中查询地图中的每个节点，这可能会耗费太多时间。 - 5lackp1x3l0x17

说实话，我不是要表现得像个混蛋一样，但这将取决于你个人的编程能力。它可能有所帮助，也可能没有。但无论如何，一次性加载整个数据集在内存消耗和运行时间上都会受到惩罚。请查看我的编辑答案。 - San Jacinto

你听起来并不像个自大的人。我是一个非常初级的程序员，这里大家提出的观点帮助我改进自己。我没有任何人可以解决我的疑问，你们都是我的唯一帮手。 - 5lackp1x3l0x17

Answer 1

这听起来像是A*算法的典型案例，但如果你不能实现Dijkstra算法，我看不出你能实现A*算法。 A*算法维基百科 编辑：这假设你有一种很好的方法来估计（但至关重要的是不要高估）从一个节点到目标的成本。

编辑2：你在邻接表表示上遇到了麻烦。我想到了一个方法，如果你为地图中的每个顶点创建一个对象，那么当有链接时，你可以直接链接到这些对象。因此，你将拥有一个包含指向相邻节点的指针（或引用）列表的对象列表。现在，如果你想访问新节点的路径，只需按照链接进行即可。请确保维护给定顶点所跟随的路径列表，以避免无限循环。

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

- San Jacinto

---

好的，现在有点棘手了。但这意味着每次运行程序都要从数据库导入所有节点，创建一个映射？ - 5lackp1x3l0x17

实际上，我再次阅读您的问题后有所领悟。列表已经在数据库中建立。在这种情况下，您可以做同样的事情，只需遵循数据库中的链接即可。根据表格结构的不同，这可能是简单的或非常困难的。理想情况下，您应该为顶点和边各有一个表格。在这种情况下，您拥有与上述完全相同的结构，只不过以DB形式存在。 - San Jacinto

Answer 2

以下是Dijkstra算法的Java版本，可帮助您了解如何在PHP中实现它。

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

- James Black

Answer 3

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

但我认为您需要Floyd算法，它可以在有向图中找到所有顶点之间的最短路径。

两种算法的数学复杂度非常接近。

我可以从维基百科上找到它们的PHP实现。

- Dmytrii Nagirniak

---

如果OP担心像听起来那样的大型数据集，由于明显的运行时原因，这些算法不会起到任何作用，更不用说多项式内存消耗了。我见过一些实现可以对集合进行聚类以减少这种情况，然后在访问每个集群时运行另一个算法...但我忘记了是否需要通过这种方式证明最短路径。 - San Jacinto