公共交通中的图论

Question

你好，

我正在开发公共交通指南软件。在欧洲和美国，谷歌地图提供了此功能，但在土耳其却没有。我的数据库中包含所有车站的纬度和经度，以及其他公交线路和车站信息。我的计划是首先使用图论（车站是顶点;边权重是站点之间的距离），连接同一公交线路上的车站;然后找到路径。之后我将在谷歌地图上展示出路线。我已经完成了第一步，连接各个车站。然而，在那之后，我发现了一个错误，如下图所示。

用户想要去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公里范围内增加车站之间的连接;但我认为这样效率低下。谢谢。

- mcs111

---

也许你可以比较两个地铁站之间的距离，并选择步行最近的两个站点？距离矩阵服务可能会有所帮助。 - MrUpsidown

感谢您的支持，但它仅适用于乘客使用2辆公交车的情况。如果两条线路不相交，需要第三条或第四条线路怎么办？ - mcs111

https://www.google.com/intl/zh-CN/landing/transit/ 这个怎么样？看起来土耳其已经有几条线路了。 - MrUpsidown

@MrUpsidown，它只显示土耳其的地铁线路。在伊兹密尔只有一条地铁线路。 - mcs111

重点是你可以为此做出贡献... - MrUpsidown

Answer 1

在 E 和 H 之间添加一条带有权重'a'的有向边。选择'a'，使得你的网络中没有任何一条边具有相同的权重'a'。例如，您可以选择将'a'设置为0，因为我确信您的网络中没有权重为零的边，这意味着某些两个站点之间没有距离。接下来，编写程序的代码，使得每当选择包含具有权重'a'的边的路线时，程序应该说：“从站点 E 到站点 H”，或连接权重'a'的边的任何节点。

否则，您可以拥有一个图表，其中每当您必须步行到一个节点时，就会有两条从一个节点到另一个节点的有向边。假设一条边的权重为0，另一条边的权重为两个站点之间的距离。确保您的程序编码方式，在遇到两个站点A和B之间有两条边时，一条重量为0，另一条重量为“x”，那么程序给出指令：“从站点A走到B，距离为'x'公里。”

- Arpitha Prasad