我正在考虑以下问题(非常粗略的描述):
假设我们有一个图,其中边被分配了一些非负成本,一个起始节点s
和一些成本常数C
。找出:
- 从起始节点
s
到任何节点N
的最短路径成本不大于C
的可达节点N
集合。 - 对于集合中的每个
e
,上述最短路径的成本。
基本上是带有成本约束的Dijkstra算法。
我的主要问题是:在图论中,这个问题的正确术语是什么?
我一直在研究“可访问性”或“可达性”,但这些似乎是错误的关键字。
最终,我在寻找一种算法,它可以在一个(不可改变的)但相当大的(潜在的~ 100百万条边)图上并行高效地回答许多这样的查询。我想检查文献,但需要关键字的提示。
更新:我的实际问题如下。
假设我们有一个大陆级别的道路网络(被建模为定向图,具有某些边缘和节点的属性,例如如果它是步行道或高速公路)。边缘成本是旅行时间。
我想回答用户查询,例如:从某个给定位置(图节点)开始,在1小时内可到达哪些节点?
我还希望为许多用户(> 10000,如果可能)并行地快速(<200-300ms,如果可能)回答这些查询。
我认为应该至少有两种优化:
- 一些预处理,例如选定“中心”节点的预计算距离矩阵。
- 如果并行进行搜索,则可以从彼此的“临时结果”中受益。
我自己有一些想法,但首先想检查文献以避免重复造轮子。