地图中的最短路径

Question

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

我试图在PHP中使用Dijkstra但我无法实现它(对我来说太难了).我觉得另一个问题是,如果我使用Dijkstra,我需要考虑所有节点,这在大图中可能效率很低.那么有人有关于上述问题的代码吗？如果有人至少向我展示了解决这个问题的方法,那将会很棒.我已经被困在这里差不多一个星期了.请帮忙.

Answer 1

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

维基百科上的A*

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

edit2:您在邻接列表表示方面遇到问题.我发现如果你为地图中的每个顶点创建一个对象,那么当有链接时你可以直接链接到这些对象.所以你所拥有的实际上是一个对象列表,每个对象都包含一个指针列表(或引用,如果你愿意)到它们所邻接的节点.现在,如果要访问新节点的路径,只需按照链接即可.确保维护一个给定顶点所遵循的路径列表,以避免无限循环.

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