验证是否所有目标节点都可以从 Python NetworkX 中的至少一个源节点访问

Question

我想知道最有效的方法是什么来验证集合 T 中的所有目标节点都可以从 Python 的 NetworkX 库中的至少一个源节点 S 访问。

对我来说，应该是一个简单的多对多Dijkstra函数调用，其中S是源节点列表输入，T是目标节点列表输入。然后我可以验证返回值是否表明至少有一个路由是成功的。这就是我将如何使用 PostgreSQL 的 pgRouting 扩展来解决这个问题，对于那些可能熟悉它的人：

pgr_dijkstra(edges_sql, start_vids, end_vids)

然而，it seems from the documentation that a function where both the sources and targets are lists does not exist。我能找到的最接近的是 multi_source_dijkstra 或 all_pairs_dijkstra.

我觉得 multi_source_dijkstra 不够，因为我不能指定多个目标节点的列表作为输入，而 all_pairs_dijkstra 太多了，因为我不想浪费时间测试之间的连接源节点或目标节点之间。此外，我完全希望我的图表本身有间隙，我只想测试原始条件——所有目标节点都只能从至少一个源节点访问。

我确信 multi_source_dijkstra 函数可以拼凑一些东西，但我希望它尽可能高效，所以我希望我只是缺少一个明显的实现，它可以做我想做的事情想要最有效率。

编辑：@abc 的图片。 red/yellow、red/pink 线和绿线代表我在 DFS 或 BFS 算法中使用的子图。此配置返回 True，声称所有红点（目标）都可以从绿点（源）到达。

Answer 1

为什么要使用最短路径算法，例如 Dijkstra 的算法？
如果您的目标是检查是否所有目标节点都可以从至少一个源节点到达，您只需要一种图遍历算法（例如，bfs and dfs）。

S = {1,2}
T = {3,4}
g = nx.fast_gnp_random_graph(6, 0.3, directed=True)

# True if all the nodes of T are reachable from at least a node in S
any(T < set(nx.bfs_tree(g,s).nodes()) for s in S)