2

我有一个有数百万个顶点和边的有向图。给出了一组顶点，假设它们被称为“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 循环会降低性能。知道如何提高效率吗？

4

3 回答 3

1

这可能有点矫枉过正，但您可能想查看Dijkstra。我过去在创建自己的虚拟节点路由表时使用它。在这种情况下，所有节点的值都为 1，这意味着每个节点的行程成本相同。

于 2011-01-04T04:33:54.620 回答
1

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

于 2011-01-04T05:02:26.403 回答
0

首先，运行强连通分量算法。然后将所有连接的组件收缩到单个节点。然后对图进行拓扑排序。然后，在一次通过中，您可以计算哪些起始节点可以到达图中的每个节点（将每个起始节点 s 初始化为集合 {s}，然后按拓扑顺序在每个节点处执行传入边的联合）。

您有一个潜在的问题，因为答案可能与 # 起始节点 * # 结束节点一样大，这可能很大。希望你有一些会收缩到单个节点的大型 SCC，因为这可以使答案更加简洁（同一个 SCC 中的所有起始节点都可以到达相同的位置，因此你只需要在你的集合中使用一个代表）。

于 2011-01-04T05:08:33.613 回答