通过php从mysql db计算两个"位置"之间的最短路径

Question

我试图找出获得/显示多个位置之间最短距离的最佳方法.为了最好地解释这一点,将其视为地图并使用以下内容.每个位置的所有距离和路径都已放入mysql数据库.

地点(信件 - >它可以到达的位置.和[]中的距离/时间)

A -> B [5]
A -> C [4]
B -> Z [1]
C -> Z [50]

所以A可以去B,需要5分钟.虽然从A到C需要4分钟.

现在我想弄清楚的是让我们说他们当前在位置A并且想要到达Z.我怎样才能让系统通过数据库并确定A - > B - > Z是最短路径与A - > C - > Z相比.

我原本打算在每个系统上进行循环,但这个设置将包含数百个不同的位置和路径.所以我已经可以看到它创建无限循环,第二个它沿着一条路径返回到起始位置.

也许这是不可能的哈哈.

任何帮助或建议将不胜感激!

提前致谢!

Answer 1

该最短路径问题可以与众多的算法来解决.Dijkstra是经典之作:

为每个节点分配距离值.对于我们的初始节点将其设置为零,对于所有其他节点将其设置为无穷大.
将所有节点标记为未访问.将初始节点设置为当前.
对于当前节点,考虑其所有未访问的邻居并计算它们的暂定距离(从初始节点开始).例如,如果当前节点(A)的距离为6,并且将其与另一个节点(B)连接的边缘为2,则到B到A的距离将为6 + 2 = 8.如果此距离小于先前记录的距离(开头的无穷大,初始节点为零),则覆盖距离.
当我们完成考虑当前节点的所有邻居时,将其标记为已访问.将不再检查受访节点; 现在记录的距离是最终的,最小的.
如果已访问所有节点,请完成.否则,将具有最小距离(从初始节点)的未访问节点设置为下一个"当前节点",并从步骤3继续.