图论——如何在一定的成本内找到从给定节点可达的节点？

Question

我正在考虑以下问题（非常粗略的描述）：

假设我们有一个图，其中边被分配了一些非负成本，一个起始节点s和一些成本常数C。找出：

• 一组节点N，可从s到达，其中从起始节点s到N中任何节点的最短路径成本不大于C
• 对于集合中的每个e，上面是最短路径的成本

基本上是有成本限制的Dijkstra。

我的主要问题是：图论中关于这个问题的正确术语是什么？

我一直在看“可访问性”或“可达性”，但这些似乎是错误的关键词。

最终，我正在寻找一种算法，它可以在一个（不可修改的）但相当大（可能约1亿条边）的图上高效地并行回答许多这样的查询。我想查看文献，但需要关于正确关键字的提示。

更新：我的实际问题如下。

假设我们有一个大陆大小的道路网络（建模为有向图，在边缘和节点上有一些属性，如人行道或高速公路）。边际成本是旅行时间。

我想回答如下用户查询：从某个给定位置（图节点）开始，哪些节点在1小时内可以到达？

我也想很快回答这些问题（

我认为至少应该有两种可能的优化：

• 一些合理大小的预计算，例如为选定的“中心”节点预计算距离矩阵。
• 如果搜索并行进行，它们可能会从彼此的“临时结果”中获利。

我自己有一些想法，但我首先想检查一下文献，以避免重新发明轮子。

Answer 1

加权图中的最短路径距离给出了图的度量空间结构。在度量空间术语中，你试图找到以s为中心的半径c的闭合球。也许有一些研究将图视为计算上可处理的离散度量空间。偏心率的概念也可以发挥作用——节点的偏心率是从该点到任何其他点的最大距离。似乎你正在试图找到一个最大子图，它的性质是子图中s的偏心率以c为界。

Dijkstra的算法可以很明显地进行修改，以满足您的需求。如果Dijkstra的算法在任何时候都要在访问节点集（已知最终距离的节点）中包含一个顶点，但结果距离超过c，则丢弃该节点，而不是将其添加到访问节点列表中。这实际上会删减从s到达的节点树。应该是合理有效的。

Answer 2

我一直在看“可访问性”或“可达性”，但这些似乎是错误的关键词。

是的，你是对的。这些是错误的关键词。

首先，让我更准确地重新定义这个问题。给定一个图G（V， E），一个节点s和一个常数c，我们要求集合R={（n， d）|s和n之间的距离是d

这个问题是可达性问题的一个推广版本，其中c是无穷大的，考虑大型图要困难得多。

现在，作为预计算的一部分，要找到集合R，必须确定s和所有其他节点之间最短路径的长度。这是伪装的所有对最短路径（APSP）问题。

因此，第一步，预计算，是在研究库中搜索一个真正快速的APSP算法，它适合您正在处理的图形类型。该算法及其实现决定了预计算的运行时间。

第二步是从算法的结果中找到一种尽可能多、尽可能高效地存储数据的方法，因为您在这里选择的数据结构和算法将决定查询的运行时间。考虑到10亿个顶点，该算法计算的最短路径数大约为10^18（从，到，距离）个三元组。如果每个值的大小为4字节，那么如果我们将所有这些数据存储在分布式哈希表中（需要额外存储），则需要大约7 EB。在这种情况下，我们最多可以实现几毫秒的查询时间。

否则，如果无法存储所有这些数据，则必须压缩数据和/或丢弃其中一些数据。现在这是一个不同的问题。您可能希望将图划分为许多小直径的子图（直径必须通过实验确定），然后仅存储子图中心节点的最短路径信息，并且在查询时必须重新运行非常有效的实现的SSSP（单源最短路径）。还有许多其他优化技术可以轻松地跨越一本书。无论你做什么，实现

在DRAM和本地磁盘中缓存查询结果是一个好主意。如果很大比例的查询是相同的，这会有很大帮助。

关于用户数，由于图是静态的，您可以并行化所有查询。您可以利用高度并行的CPU和GPU。

最后，可以优化为处理查询本身而编写的代码。深入理解编译器优化和计算机体系结构有助于大大缩短查询时间。

Answer 3

您正在处理的问题的正确术语是“最短路径算法”。可达性问题（即Warshal）处理的问题是“节点a和B之间是否存在路径？”它有一个二元答案，在这种情况下你不需要权重，你只需要寻找边。但在您的情况下，您需要考虑在每种情况下从节点A到节点B所需的时间。

现在，没有“确切”适合这个问题，因为Dijktra、Floyd、BFS或DFS的一个小变化可以用来解决这个问题，但是你有一个额外的复杂性，因为图的大小，这对于理解如何构建很重要你的解决方案。使用哪种算法取决于您的时间限制和可用硬件的具体组合。

您的问题有两种算法解决方案（我假设您已经将所有边存储在某个位置，并且您可以以某种方式查询此数据库）：

>

在一个理想的（想象的）世界中，你会运行弗洛伊德算法，将结果矩阵保存在像Redis这样的东西中，仅此而已，你可以在不到10毫秒的时间内服务你的请求，如果客户端数量增加，你可以添加更多Redis服务器根据需要，因为图形不太可能经常更改（因为在您的特定问题中，您有道路信息）。这个问题是解决方案的空间复杂度，最好的一点是所有的东西都是预计算的，这意味着您对请求的响应时间是最小的。为了能够实现一些变化，你需要大量的空间，即使是一个redis集群，数据库存储在磁盘上（是的，磁盘，不是内存），所有带有SSD的服务器都应该足够了，当并发客户端的数量增加时，这个选项可以很好地扩展增长和时间反应相当快。但是你是否可以使用这个解决方案取决于你的图中节点的数量：即使你需要使用每个边预先计算距离，你只需要空间来存储一个NxN的矩阵，即图中节点的数量，如果这个矩阵适合redis，然后你可以使用这个算法，预计算所有节点之间的“距离”（在你的情况下，这是成本的总和，也就是“旅行时间”）。稍后，当你收到一个请求时，你需要查询得到的矩阵来获取旅行时间小于给定值的所有节点，在redis中存储这个矩阵时，还有一个额外的优化，可以让你很快地获取节点编号使用排序集。

然后你有第二个解决方案，就是修改Dijktra，BFS或DFS，根据成本来削减搜索，仅此而已。在这种情况下，您已经放弃了Floyd，因为空间复杂度很高，这意味着您的图在节点和边上都相当大。在这种情况下，使用任何算法的变体，解决方案几乎是相同的，这使得不同之处在于您如何存储图形。所有3种算法都可以修改，以便在所需时间内高效响应，但为了支持10k客户端，用于存储图形的数据库会有所不同。这里你有另外两个选择：

• 使用标准的SQL/NoSQL数据库：这个数据库应该以某种方式进行切分，因为它应该服务于在图形上运行搜索的代码服务器（复数，因为C10K问题）。我建议您根据图形数据本身的大小继续这方面的研究，但如果您设法将所有数据放在Cassandra集群或类似技术中，它可以根据您想要的响应时间进行优化，并且扩展得非常好
• 您利用了图形实际上是一个“地图”的事实，并找到了一种对数据运行距离查询的方法：这可能需要您更改存储图形的方式，以添加纬度和经度之类的内容。因此，与其针对完整的图形运行算法（这很荒谬），不如利用这样一个事实来优化整个过程：给定给定节点的一定时间，您可以将其转换为以英里为单位的距离D（近似值，为了安全起见，您可以加上10-20英里）然后在数据库上运行一个查询，以获取距离为D的所有节点，然后对这个小图运行您选择的算法。请务必注意，使用此方法从数据库中提取的图形已经为您提供了解决方案的近似值，前提是边缘中的实际移动时间与移动距离成一定比例（这并不总是正确的，这就是为什么它是近似值）。要在小范围内实现这一点，您可以使用PostgreSQL PostGIS，它允许您运行此类查询，但您需要在此处进行一些研究，以找到最适合您的解决方案

希望有帮助！