从点之间的距离计算图形
Computing graph from the distances between points
我有一组地理点（纬度、经度），我想计算一个有向图，其中：
- 节点就是那些点
- 一条边X->Y（在节点X和Y之间）存在如果X 和 Y 之间的最快路径不经过另一个节点 Z.
我能够计算任意一对节点之间路径的持续时间。
现在，我正在执行以下操作：
- 计算每对节点之间的持续时间
- 对于每对节点X,Y,X之间有一条边和 Y 如果没有节点 Z 这样 X->[=21= 的持续时间]Z plus Z->Y的持续时间与X->Y.
的持续时间
我已经针对节点的一个子集测试了这种方法，它似乎有效，但由于我有大约 2000 个节点并且计算节点之间的持续时间在计算上很昂贵（因为它涉及计算最短路径），我想知道有没有更好的方法。
一些额外的（可能不相关的）信息：
- 节点是巴士站位置，取自 GTFS 提要
- 我正在使用 http://project-osrm.org/
计算最短路径持续时间
任何帮助将不胜感激
我将从 运行 进行 Delaunay 三角剖分开始，这将使您了解路径结构“应该”是什么样子（理论上）。从理论上讲，一旦有了 delaunary triangulation，就很容易找到最短路径。但是在实践中，您使用的是道路网络而不是 point-to-point 距离，因此您必须挑战这些假设。
首先建立一个给定Delaunay三角剖分的方法。三角测量的示例如下所示。假设 HJG 点位于市中心，而它周围的点是环绕它的高速公路。以 65 英里/小时左右的速度限制为例。这意味着从 ABCG 出发可能比 AHG 更快。
对于 Delaunay 三角剖分中的每条边。确定边缘在两个方向上的持续时间。这将为您提供初始权重（如果您可以确定 AH 的最短路径实际上是 ABH，它也可能影响三角测量）。如果没有办法绕过更快的路线。 ABCG 比 AHG 示例更快。然后你可能在这一点上完成了。如果不是，你将不得不尝试收缩边缘，这取决于你的数据，可能需要做所有的路线，因为你不能真正确定一些模糊的路径允许它更快。遗憾的是，三角测量无法解释边缘之间的速度差异。
如果您可以设置它来告诉您它确实经过了哪一点，那么您就可以避免在所有路径上都必须 运行 它。 IE：如果你可以说让它告诉你最快的路径AF，它说它使用AHGF，那么你可以合理地确定AHG和HGF是AG和HF之间的最短路径，你不需要运行那些。但是，如果你发现AF居然走的是ABCEF，那么显然两条路线之间的速度差异很大，你也应该检查到AG的最快路线，确保它实际上是AHG。每当您发现更快的边缘时，一定要添加到三角测量中。您实际上可以添加多个边。基本上这里的想法是三角测量让你知道如果速度无关紧要什么应该是最快的路线。但是，您需要确认或拒绝该假设。基本上每个节点。通过 BFS 找到到所有点的最短路径。走最长的路，探索它。
为了帮助#3，它可能有助于图中边的顶点路径覆盖。创建从每个点到所有最远点的路径，直到覆盖所有点。 IE：ABCD ABCE AHGF AHJKL AIK（也是方向相反的顺序）。然后你可以 运行 从 AD、AE、AF、AL 和 AK 的最短路径。如果这些路径与预期路径匹配，那么您就完成了。如果没有，您将按照上面#3 所用的方法不断改进。不过，最坏的情况是，我不确定是否有办法比理论上的所有最短路径都快得多，这种方法大致为 O(VE)。
理论上 #4 需要从每个顶点开始。但是，如果连接路径作为最短路径是有效的，则可以跳过顶点，因此我可能建议开始检查具有最少 (un-validated?) 边的顶点。不过，您可能需要做所有对才能 100% 确定只有最短的边连接每个节点。
为了测试，我建议这样做：随机 select 说出 2000 分中的 10-200 分。 运行 那些 10-200 点的算法。然后 运行 这些点上的所有路径。如果他们不同意，请仔细查看他们不同意的原因。请随意在您的答案和评论中添加任何“例外”案例。重复多次，看是否有异议。记录所有分歧。如果没有分歧，请在整个 2000 个点集上尝试 运行ning。我会强烈建议在第 2 步之后进行此测试。Delaunay 图有可能非常接近最优，具体取决于您的数据集。
我有一组地理点（纬度、经度），我想计算一个有向图，其中：
- 节点就是那些点
- 一条边X->Y（在节点X和Y之间）存在如果X 和 Y 之间的最快路径不经过另一个节点 Z.
我能够计算任意一对节点之间路径的持续时间。 现在，我正在执行以下操作：
- 计算每对节点之间的持续时间
- 对于每对节点X,Y,X之间有一条边和 Y 如果没有节点 Z 这样 X->[=21= 的持续时间]Z plus Z->Y的持续时间与X->Y. 的持续时间
我已经针对节点的一个子集测试了这种方法，它似乎有效，但由于我有大约 2000 个节点并且计算节点之间的持续时间在计算上很昂贵（因为它涉及计算最短路径），我想知道有没有更好的方法。
一些额外的（可能不相关的）信息：
- 节点是巴士站位置，取自 GTFS 提要
- 我正在使用 http://project-osrm.org/ 计算最短路径持续时间
任何帮助将不胜感激
我将从 运行 进行 Delaunay 三角剖分开始，这将使您了解路径结构“应该”是什么样子（理论上）。从理论上讲，一旦有了 delaunary triangulation，就很容易找到最短路径。但是在实践中，您使用的是道路网络而不是 point-to-point 距离，因此您必须挑战这些假设。
首先建立一个给定Delaunay三角剖分的方法。三角测量的示例如下所示。假设 HJG 点位于市中心，而它周围的点是环绕它的高速公路。以 65 英里/小时左右的速度限制为例。这意味着从 ABCG 出发可能比 AHG 更快。
对于 Delaunay 三角剖分中的每条边。确定边缘在两个方向上的持续时间。这将为您提供初始权重（如果您可以确定 AH 的最短路径实际上是 ABH，它也可能影响三角测量）。如果没有办法绕过更快的路线。 ABCG 比 AHG 示例更快。然后你可能在这一点上完成了。如果不是，你将不得不尝试收缩边缘，这取决于你的数据，可能需要做所有的路线，因为你不能真正确定一些模糊的路径允许它更快。遗憾的是，三角测量无法解释边缘之间的速度差异。
如果您可以设置它来告诉您它确实经过了哪一点，那么您就可以避免在所有路径上都必须 运行 它。 IE：如果你可以说让它告诉你最快的路径AF，它说它使用AHGF，那么你可以合理地确定AHG和HGF是AG和HF之间的最短路径，你不需要运行那些。但是，如果你发现AF居然走的是ABCEF，那么显然两条路线之间的速度差异很大，你也应该检查到AG的最快路线，确保它实际上是AHG。每当您发现更快的边缘时，一定要添加到三角测量中。您实际上可以添加多个边。基本上这里的想法是三角测量让你知道如果速度无关紧要什么应该是最快的路线。但是，您需要确认或拒绝该假设。基本上每个节点。通过 BFS 找到到所有点的最短路径。走最长的路，探索它。
为了帮助#3，它可能有助于图中边的顶点路径覆盖。创建从每个点到所有最远点的路径，直到覆盖所有点。 IE：ABCD ABCE AHGF AHJKL AIK（也是方向相反的顺序）。然后你可以 运行 从 AD、AE、AF、AL 和 AK 的最短路径。如果这些路径与预期路径匹配，那么您就完成了。如果没有，您将按照上面#3 所用的方法不断改进。不过，最坏的情况是，我不确定是否有办法比理论上的所有最短路径都快得多，这种方法大致为 O(VE)。
理论上 #4 需要从每个顶点开始。但是，如果连接路径作为最短路径是有效的，则可以跳过顶点，因此我可能建议开始检查具有最少 (un-validated?) 边的顶点。不过，您可能需要做所有对才能 100% 确定只有最短的边连接每个节点。
为了测试，我建议这样做：随机 select 说出 2000 分中的 10-200 分。 运行 那些 10-200 点的算法。然后 运行 这些点上的所有路径。如果他们不同意，请仔细查看他们不同意的原因。请随意在您的答案和评论中添加任何“例外”案例。重复多次，看是否有异议。记录所有分歧。如果没有分歧，请在整个 2000 个点集上尝试 运行ning。我会强烈建议在第 2 步之后进行此测试。Delaunay 图有可能非常接近最优，具体取决于您的数据集。