题
我有一个有针对数百万个顶点和边缘的图形。给出了一组顶点,假设它们称为“ start_points”。还给出了另一组称为“ end_points”的顶点。问题是找到可以从哪些start_point到达哪些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 .....
....
可能无法从任何start_point到达某些end_point。
现在,问题是:实施它的最有效方法是什么?
我尝试从每个start_point一对一开始,并使用深度优先搜索(或BFS,它确实会大大改变运行时)。但是,这需要很多时间,因为有很多start_point(也有很多end_points)。
可以优化搜索,因为start_point的追踪路径之间存在巨大的重叠。一个人需要记住哪些路径可以到达哪些end_points。完成此操作的最有效方法是什么?这可能是众所周知的问题,但我还找不到解决方案。
1月6日编辑:
我试图实现HighBandWidth的想法(以类似于Keith Randall提出的方式):对于每个节点,如果此节点不是启动或终点,请将所有输入连接到输出,然后删除节点。
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
这开始非常快,很快变得非常缓慢,主要是因为剩余节点的输入/输出计数变得非常大,并且嵌套以杀死性能。知道如何使其更有效吗?
解决方案
只需修剪图表即可摆脱所有没有出现在start节点或结束节点中的节点,然后用从其入站节点到出站目标的边缘代替它们。完成此操作后,请浏览所有其他节点(启动或结束节点),并将其从入站节点添加到其出站节点,而不会删除这些节点。在几个类似Djikstra的迭代中,您应该离开开始边缘。
其他提示
这可能是过分的,但您可能想检查一下 Dijkstra. 。我过去在创建自己的虚拟节点路由表时使用过它。在这种情况下,您的所有节点的值为1,这意味着每个节点的成本都相同。