php - 在城市中应用最短路径算法

Question

我的记录中有 6 个城市。孟买、布洛尔、Hbad、德里、钦奈、浦那。并记录具体到每个城市。

当用户访问我的页面时，我想根据位置相关性显示记录。我想为此使用最短距离算法。

从用户的 IP，我可以得到他的位置(城市或 lang-lati)。我想到了计算用户与上述每个城市的距离。那，我应该选择最近的那个来显示记录。

有什么更好的方法吗？我正在使用 php。

请在实现层面谈谈...

Answer 1

您可以将您的城市表示为图中的节点，将它们之间的距离表示为边上的权重，然后应用 Dijkstra 算法 (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)如果你想获得前 5 个最短距离，你可以使用 Yen 的算法或 A* ( http://en.wikipedia.org/wiki/A *_search_algorithm )

语言:您必须创建一个加权图(是否定向，取决于您)。图中的节点可以是城市的名称(或者，如果您对城市有更多详细信息，可以使用 City 类型的对象)。城市之间的距离将由它们之间的加权边表示。

运行 Dijkstra，您将必须指定一个起始节点和一个结束节点(在您的 casses 中，您的用户当时所在的城市和他想去的城市)。该算法将返回最短的距离，并且用一个小的实现可以打印从源到目的地的整个路径。