查找与n相连的所有节点

Question

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

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

但是这个过程非常缓慢，我猜想这是因为在图中有很多节点与i没有任何连接。有没有一种优化这个过程的方法？我已经确保那些不可能与其他节点相连的节点不会最终出现在A中。

- Gabriella Lapesa

---

你使用的语言是什么？Python？你应该添加标签。 - DrakaSAN

图是仅有定向，还是也无环的呢？ - Patrick Maupin

感谢您的编辑，我正在使用Python。该图是无环的。 - Gabriella Lapesa

Answer 1

有一个内置命令：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]}

问题标题表明你只想知道可达节点而不是路径。在这种情况下，使用深度优先搜索或广度优先搜索。文档可以在这里找到。例如：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

- Joel

---

或者，您可以使用 nx.descendants 查找可达节点。请参见 https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.dag.descendants.html - JanLikar

Answer 2

你可以尝试使用构建算法来查找所有节点对之间的最短路径，而不是迭代所有节点对并为每个节点对获取最短路径（这样做每次都不会利用过去的知识）。

- Roy Shahaf

---

那么你的意思是不使用networkx中预定义的函数？ - Gabriella Lapesa

我不熟悉networkx中预定义的函数，但使用现有函数的组合（或者如果存在的话，适合您需求的专用函数），可能能够达到所需的改进。 但显然，您目前的方法相当直接，这意味着a.它有效（您不必费力证明），但b.它很慢。 - Roy Shahaf

非常感谢您的建议。我会尝试自己实现并比较速度，但我猜测包中的内置函数比我的代码更好。 - Gabriella Lapesa

Answer 3

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

请注意，为了清晰起见，该答案并没有进行任何优化（除了最初的拓扑排序）。它执行了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))，你可以缩短它。

- Patrick Maupin