带步行路段的路线规划

Question

我正在开发一个应用程序，它可以显示使用 public 交通方式（目前只有公交车）的最短路线。它应该包括人们可以步行一段距离到下一站而不是乘坐另一辆公共汽车（如果它更短）的部分。

1. 地图的数据结构应该是什么？我想到了带有公交车站节点的图形结构。和以距离为权重的顶点。

2. 即使我使用算法 (dijkstra) 找到了最短路径，如何将步行部分实现到逻辑中。

Answer 1

如果没有很多额外的信息，很难给你一个很好的答案，但让我了解一些基础知识。这应该足以让您继续前进，但是您将需要做额外的工作来开发您的解决方案。

1. 一般来说，您的数据结构将类似于代表目的地的节点或 waypoints（例如公交车站或地址）。您的关系将是带有相关费用的交通方式。例如，您可以步行或乘坐公共汽车从 point/node A 到达 point/node B。这是两种不同的关系，在时间和金钱方面有不同的"costs"。
2. 通常，您需要使用 "weighted shortest path" 算法来找到从 A 点到 B 点的最佳路径。Neo4j 为您提供最短路径函数，但在您的情况下，您需要为你的关系分配权重，然后计算最短路径，而不是基于图表中 "hops" 的数量，而是基于一些总体成本指标（时间、金钱等）。

Ian Robinson wrote a great post on how to do weighted shortest paths in neo4j。所以你应该按照这样的模板作为起点。

虽然你有一堆设计问题要回答。您想要时间、金钱、精力或某种组合方面的最短路径吗？答案将影响您的图形设计和查询策略。