找到连接到 n 的所有节点

Question

我需要找到有向图中每对节点之间的所有最短路径。我正在做的是：

for i in A.nodes()
    for y in A.nodes()
        paths = nx.all_shortest_paths(G,i,y)

但是我猜这很慢，因为在图中有很多节点无论如何都与 i 没有连接。有没有办法优化这个过程？我已经在注意不可能连接到其他节点的节点不会在 A 中结束。

Answer 1

您可以尝试一种构造性算法来查找所有节点对之间的所有最短路径，而不是遍历所有节点对并为每对节点获取最短路径（每次都不会使用过去的知识）。

Answer 2

正如 Roy Shahaf 所说，您可以构建一个不会丢失您已经完成的工作的建设性算法。此外，由于图是有向的，如果您先对图进行拓扑排序，您会立即优化 50%，因为您唯一可能到达的节点是起始节点之后的节点。我发布了一个较早的答案（不使用 nx）进行拓扑排序，然后找到从一个节点到每个其他节点的所有距离

请注意，为清楚起见，该答案根本没有优化（初始拓扑排序除外）。它相当于 for n1 in G for n2 in G，但正如我所说，如果将节点放在列表中，然后对第一个节点的整个列表进行索引，然后对列表中的所有节点进行索引，则可以将其缩减在第一个之后的第二个，例如(nlist[i], nlist[j]) for i in range(len(nlist)) for j in range(i+1, len(nlist))

Answer 3

内置命令： single_source_shortest_path_length(G, source) 为您提供源和每个可达节点之间的最短路径。

import networkx as nx
G=nx.DiGraph()
G.add_edges_from([(1,2), (2,3), (3,4), (1,5), (2,5), (6,7)]) #6,7 not reachable from 1
nx.single_source_shortest_path(G,1)
>{1: [1], 2: [1, 2], 3: [1, 2, 3], 4: [1, 2, 3, 4], 5: [1, 5]}

题名表明你只想知道可达节点而不是路径。在这种情况下，请使用深度优先或广度优先搜索。文档是 here。例如：dfs_postorder_nodes(G, source=None) 为可从源到达的节点提供迭代器。它们出现的具体顺序是深度优先搜索后序。

for reachable_node in nx.dfs_postorder_nodes(G,source=1):
   print reachable_node
>4
>3
>5
>2
>1

找到连接到 n 的所有节点

Find all nodes connected to n

python

networkx