c++ - 有向图中的高效搜索

Question

我有一个包含数百万个顶点和边的有向图。给定了一组顶点，我们假设它们被称为“START_POINTS”。还给出了另一组称为“END_POINTS”的顶点。问题是找出从哪个 START_POINTS 可以到达哪个 END_POINTS。

这是一个例子:

START_POINTS: S1 S2 S3 S4 S5 S6 S7 ... 
END_POINTS  : E1 E2 E3 E4 E5 E6 E7 ... 

该算法应该能够说明以下内容:

S1 can reach to E1, E2, E6
S2 can reach to E9, E10
S3 cannot reach any END_POINT
S4 can reach to .....
....

某些 END_POINTS 可能无法从任何 START_POINT 到达。

现在的问题是:最有效的实现方式是什么？

我尝试从每个 START_POINT 一个接一个开始，并使用深度优先搜索(或 BFS，它确实会大大改变运行时间)找到可到达的 END_POINTS。但是，这会花费很多时间，因为有太多的 START_POINTS(也有很多 END_POINTS)。

可以优化搜索，因为 START_POINTS 的跟踪路径之间存在巨大的重叠。人们需要记住哪些路径可以到达哪些 END_POINTS。实现这一目标的最有效方法是什么？这可能是众所周知的问题，但我还找不到解决方案。

1 月 6 日编辑:

我尝试实现 highBandWidth 的想法(以类似于 Keith Randall 提出的方式):对于每个节点，如果该节点不是 START 或 END 点，则将所有输入连接到输出，然后删除该节点。

foreach NODE in NODES
    Skip if NODE is START_POINT or END_POINT
    foreach OUTPUT_NODE of NODE
        Disconnect NODE from INPUT_NODE
    end
    foreach INPUT_NODE of NODE
        Disconnect NODE from INPUT_NODE
        foreach OUTPUT_NODE of NODE
            Connect INPUT_NODE to OUTPUT_NODE
        end
    end
    Remove NODE from NODES
end

这开始非常快，很快变得非常慢，主要是因为剩余节点的输入/输出计数变得非常大并且嵌套 for 循环会降低性能。知道如何提高效率吗？

Answer 1

只需修剪图形以去除所有未出现在起始节点或结束节点中的节点，将它们替换为从入站节点到出站目标的边。一旦完成，遍历所有其他节点(开始或结束节点)，并将边从它们的入站节点添加到它们的出站节点，而不删除这些节点。在几个类似 Djikstra 的迭代中，您应该留下从开始到结束的边缘。