php - 通过PHP从MySQL数据库计算两个 "locations"之间的最短路径

Question

我正在尝试找出获取/显示多个位置之间最短距离的最佳方法。为了最好地解释这一点，请将其视为 map 并使用以下内容。每个位置的所有距离和路径都已经放入 MySQL 数据库中。

位置(字母 -> 它可以到达的位置。以及 [] 中的距离/时间)

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

所以 A 可以去 B 并且需要 5 分钟。从 A 到 C 需要 4 分钟。

现在我想弄清楚的是假设有人说他们目前在位置 A 并想去 Z。我怎样才能让系统通过数据库并确定 A -> B ->与 A -> C -> Z 相比，Z 是最短路径。

我最初想在每个系统上做一个循环，但这个设置将包含数百个不同的位置和路径。所以我已经可以看到它在沿着一条路径回到起始位置的那一刻创建了无限循环。

也许这是不可能的。

如有任何帮助或建议，我们将不胜感激!

Answer 1

Shortest Path Problem可以用很多算法来解决。 Dijkstra是经典:

1. 为每个节点分配一个距离值。对于我们的初始节点将其设置为零，对于所有其他节点将其设置为无穷大。
2. 将所有节点标记为未访问。将初始节点设置为当前节点。
3. 对于当前节点，考虑其所有未访问的邻居并计算它们的暂定距离(与初始节点的距离)。例如，如果当前节点 (A) 的距离为 6，并且连接它与另一个节点 (B) 的边为 2，则通过 A 到 B 的距离将为 6+2=8。如果这个距离小于之前记录的距离(开始无穷大，初始节点为零)，覆盖距离。
4. 当我们完成对当前节点的所有邻居的考虑后，将其标记为已访问。不会再次检查已访问的节点；它现在记录的距离是最终的和最小的。
5. 如果所有的节点都被访问过，结束。否则，将距离(初始节点)最小的未访问节点设置为下一个“当前节点”，并从第3步继续。