地图中的最短路径
我使用 mysql 中的标准化邻接表设计了一个加权图。现在我需要找到两个给定节点之间的最短路径。
我尝试在 php 中使用 Dijkstra 但我无法实现它（对我来说太难了）。我觉得的另一个问题是，如果我使用 Dijkstra，我需要考虑所有节点，这在大图中可能效率很低。那么有人有与上述问题相关的代码吗？如果有人至少向我展示解决这个问题的方法，那就太好了。我已经被困在这里快一周了。请帮忙。
I have designed a weighted graph using a normalized adjacency list in mysql. Now I need to find the shortest path between two given nodes.
I have tried to use Dijkstra in php but I couldnt manage to implement it (too difficult for me). Another problem I felt was that if I use Dijkstra I would need to consider all the nodes, that may be perhaps very inefficient in a large graph. So does anybody has a code relating to the above problem? It would be great if somebody atleast shows me a way of solving this problem. I have been stuck here for almost a week now. Please help.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这听起来像是 A* 算法的经典案例，但如果你不能实现 Dijkstra，我就看不到你实现 A*。
维基百科上的 A*
编辑：这假设您有一个很好的方法来估计（但是至关重要的是（不要高估）从一个节点到达目标的成本。
edit2：您在邻接列表表示方面遇到问题。我突然想到，如果为地图中的每个顶点创建一个对象，那么当存在链接时，您可以直接链接到这些对象。因此，您本质上拥有的是一个对象列表，每个对象都包含指向它们相邻节点的指针（或引用，如果您愿意的话）列表。现在，如果您想访问新节点的路径，只需点击链接即可。请务必维护给定顶点所遵循的路径列表，以避免无限循环。
至于每次需要访问某些内容时查询数据库，无论如何您都需要这样做。您最好的希望是仅在需要时才查询数据库...这意味着仅当您想要获取图表中特定边上的信息或图表中一个顶点的所有边上的信息时才查询它（后者可能会）是更好的路线），因此您只能偶尔使用缓慢的 I/O，而不是一次性使用巨大的块。
This sounds like a classic case of the A* algorithm, but if you can't implement Dijkstra, I can't see you implenting A*.
A* on Wikipedia
edit: this assumes that you have a good way to estimate (but it is crucial you don't over-estimate) the cost of getting from one node to the goal.
edit2: you are having trouble with the adjacency list representation. It occurs to me that if you create an object for each vertex in the map then you can link directly to these objects when there is a link. So what you'd have essentially is a list of objects that each contain a list of pointers (or references, if you will) to the nodes they are adjacent to. Now, if you want to access the path for a new node, you just follow the links. Be sure to maintain a list of the paths you've followed for a given vertex to avoid infinite cycles.
As far as querying the DB each time you need to access something, you're going to need to do this anyway. Your best hope is to only query the DB when you NEED to... this means only querying it when you want to get info on a specific edge in the graph, or for all edges for one vertext in the graph (the latter would likely be the better route) so you only hit the slow I/O once in a while rather than gigantic chunks all at once.
这是 Dijkstra 算法的 Java 版本，可以帮助您了解如何在 PHP 中实现它。
http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29
Here is a literate version of the Dijkstra algorithm, in Java, that may help you to figure out how to implement it in PHP.
http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29
Dijkstra 算法返回从给定顶点到其他顶点的最短路径。
您可以在 Wiki 中找到其伪代码。
但我认为你需要 Floyd 算法来找到所有顶点之间的最短路径在有向图中。
两者的数学复杂度非常接近。
我可以找到 PHP 实现来自他们俩的维基百科。
Dijkstra algorithm returns shortest paths from given vertex to other vertexes.
You can find its pseudo-code in Wiki.
But I think you need Floyd algorithm which finds shortest paths between all vertexes in a DIRECTED grapth.
The mathematical complexity of both are pretty close.
I could find PHP implementation from the Wiki for both of them.