JGraphT 好 Performance/Storage 具有数百万动态 Nodes/Edges
JGraphT Good Performance/Storage with Millions of Dynamic Nodes/Edges
我试图在具有一百万个节点的图中找到最短路径。平均而言，每个节点可能有 20 条有向边，因此它相当大。
除此之外，有没有办法实时（动态）调整边的权重？
我的意思是我希望能够通过时间参数来路由图表。根据该时间参数，它将边缘权重乘以一定数量。
你可能有这样的数据：
- 节点A
- 节点 B
- 权重为 5 的边 1（A 到 B）
- 权重为 3 的边 2（也是从 A 到 B）
我可能会调用一个函数：
graph.getShortestPath(A, B, 8) // From node A to B at 8am
graph.getShortestPath(A, B, 16) // From node A to B at 4pm
时间参数会影响边的权重。例如。当一条边被遍历时，我想确定该边的位置并将其权重乘以一个取决于时间参数的因子。
Java（或者更好，Kotlin）中是否有一个简单的 JGraphT 示例可以说明这一点？
在如此大的图形上进行时间依赖路由绝非易事，尤其是当您正在寻找动态更新时。这将需要高度复杂的算法和存储方法。毫不奇怪，有大量关于这个主题的学术文献。
对于jgrapht，先阅读user guide. Next, have a look at the various Shortest Path Algorithms that are currently included in jgrapht. For examples on how to use them, see the test classes。您可能想使用一种 Contraction Hierarchy 算法。您需要支付初始成本来执行算法的初始化，但随后在大图上的最短路径查询非常快。
为了更快地存储图形，您可能想尝试 jgrapht-opt 包中的优化稀疏图形表示。
目前 none 的算法提供了一些增量机制来处理动态权重变化。此外，目前不包括 time-dependent 算法。您可以做的是创建图形的多个时间快照，例如每 15 分钟的行驶速度快照。当计算从 9.05 开始的路线的最短路径时，您将使用 9.15 快照来近似旅行时间。对于快照，请使用 AsWeightedGraph 视图，您可以通过该视图提供同一基础图形的不同加权视图。
我试图在具有一百万个节点的图中找到最短路径。平均而言，每个节点可能有 20 条有向边，因此它相当大。
除此之外，有没有办法实时（动态）调整边的权重？
我的意思是我希望能够通过时间参数来路由图表。根据该时间参数，它将边缘权重乘以一定数量。
你可能有这样的数据：
- 节点A
- 节点 B
- 权重为 5 的边 1（A 到 B）
- 权重为 3 的边 2（也是从 A 到 B）
我可能会调用一个函数：
graph.getShortestPath(A, B, 8) // From node A to B at 8am
graph.getShortestPath(A, B, 16) // From node A to B at 4pm
时间参数会影响边的权重。例如。当一条边被遍历时，我想确定该边的位置并将其权重乘以一个取决于时间参数的因子。
Java（或者更好，Kotlin）中是否有一个简单的 JGraphT 示例可以说明这一点？
在如此大的图形上进行时间依赖路由绝非易事，尤其是当您正在寻找动态更新时。这将需要高度复杂的算法和存储方法。毫不奇怪，有大量关于这个主题的学术文献。
对于jgrapht，先阅读user guide. Next, have a look at the various Shortest Path Algorithms that are currently included in jgrapht. For examples on how to use them, see the test classes。您可能想使用一种 Contraction Hierarchy 算法。您需要支付初始成本来执行算法的初始化，但随后在大图上的最短路径查询非常快。 为了更快地存储图形，您可能想尝试 jgrapht-opt 包中的优化稀疏图形表示。
目前 none 的算法提供了一些增量机制来处理动态权重变化。此外，目前不包括 time-dependent 算法。您可以做的是创建图形的多个时间快照，例如每 15 分钟的行驶速度快照。当计算从 9.05 开始的路线的最短路径时，您将使用 9.15 快照来近似旅行时间。对于快照，请使用 AsWeightedGraph 视图，您可以通过该视图提供同一基础图形的不同加权视图。