php - 公共(public)交通中的图论

Question

你好，

我现在正在开发公共(public)交通指南软件。在欧洲，美国谷歌地图提供了这一点，但在土耳其则没有。我有一个数据库，其中包含所有站点的经纬度以及其他公交线路、站点信息。在我的计划中，首先我将使用图论(站点是顶点；边缘权重是站点之间的距离)并连接同一条公交线路上的站点；然后寻找路线。之后我将在谷歌地图上演示路线。我已经完成了第一步，连接站点。然而，之后我发现我的计划有一个错误，如图所示。人想靠近 A 到 K，程序应该说

1. 走到A站
2. 在A站坐8路车
3. 在E站下了8路车
4. 走到H站
5. 在H站上了970路公交车
6. 在K站下了970路公交车

但是，E 站和 H 站之间没有连接。因此，图算法无法找到从 A 到 K 的路线。我应该定义 E 和 H 之间的步行路径。然而，这只是城市的小示范全市6500多个车站。我怎么解决这个问题？我有一个想法，即在 1 公里范围内的站点之间添加连接；但我认为这是低效的。谢谢。

Answer 1

在 E 和 H 之间添加一条有向边，权重为“a”。以这样一种方式选择“a”，即网络中的边权重都不具有相同的权重“a”。例如，您可以选择“a”为 0，因为我确信您的网络中没有任何边的权重为零，因为这意味着某些两个站之间没有距离。接下来，以这样的方式编写您的程序，只要选择了一条包含权重为“a”的边的路线，程序就会说“从站 E 走到站 H”或任何一个节点连接权重为“a”的边。

否则，您可以得到一个图，这样每当您需要行走时，从一个节点到另一个节点都有两条有向边。假设一条边的权重为 0，另一条边的权重为两个站之间的距离。确保你的程序以这样一种方式编码，当在 A 站和 B 站之间遇到两条边时，一条权重为 0，另一条为 'x'，然后程序给出指令，“从站点 A 到 B，距离为 'x' 公里。"