Networkx：获取节点之间的距离

Question

我是NetworkX的初学者，我正在尝试找到一种方法来检测哪些节点之间的距离为x。

我已经开始使用这个算法获取所有的节点对：

path=nx.all_pairs_dijkstra_path(G)

但我仍然不确定如何使用for循环检测节点之间的距离。

我会非常感谢任何帮助。谢谢

- michaelI

---

你指的是哪一个距离？是两个节点之间的最小边数吗？ - GeckStar

例如，我有一个由5个节点[A、B、C、D、E]组成的直线路径图，其中边缘为(A,B) (B,C) (C,D) (D,E)，我想知道A节点和D节点之间的距离。当然，我将在一个更大的程序中使用它，但我想知道我应该使用什么方法。谢谢。 - michaelI

Answer 1

NetworkX有自动计算加权和非加权图的最短路径（或仅路径长度）的方法。请确保根据您的用例使用正确的方法。 networkx.all_pairs_shortest_path - 计算非加权图中所有节点之间的最短路径 networkx.all_pairs_shortest_path_length - 计算非加权图中所有节点之间最短路径的长度

networkx.all_pairs_dijkstra_path - 用于计算加权图中所有节点之间的最短路径。

networkx.all_pairs_dijkstra_path_length - 用于计算加权图中所有节点之间最短路径的长度。

每个方法在执行时，都会计算一个节点的字典矩阵（“字典的字典”），其中最短路径或最短路径长度作为值。我将通过一个示例来演示这一点：

>>> import networkx as nx
>>> G = nx.Graph()
>>> G.add_nodes_from(["A", "B", "C", "D", "E"])
>>> G.add_edges_from([("A", "B"), ("B", "C"), ("C", "D"), ("D", "E")])
>>> sp = dict(nx.all_pairs_shortest_path(G))
>>> sp["A"]["E"]
['A', 'B', 'C', 'D', 'E']
>>> spl = dict(nx.all_pairs_shortest_path_length(G))
>>> spl["A"]["E"]
4

如您所见，我生成了一个有五个节点的图，并用边将每个节点连接到下一个节点。我在sp中存储了最短路径的矩阵，在spl中存储了最短路径长度的矩阵。当我需要知道两个节点之间的最短路径时，例如节点"A"和节点"E"，我只需像访问矩阵或字典一样访问sp：sp["A"]["E"]。它将返回两个节点之间的整个最短路径。最短路径长度的方法也是类似的，但它只返回任意两个给定节点之间的边数。

下面的代码片段可能会更清楚地说明我所说的字典矩阵。如果我请求节点"A"在sp中的所有条目，它将返回另一个字典，其中包含每个其他节点的条目：

>>> sp["A"]
{'B': ['A', 'B'], 'A': ['A'], 'E': ['A', 'B', 'C', 'D', 'E'], 'C': ['A', 'B', 'C
'], 'D': ['A', 'B', 'C', 'D']}

如果您想使用for循环检查所有节点之间的距离，只需迭代矩阵第一个字典的键，然后再迭代该字典内部的字典即可。这比听起来要容易得多：

>>> for node1 in spl:
...   for node2 in spl[node1]:
...     print("Length between", node1, "and", node2, "is", spl[node1][node2])
...
Length between B and B is 0
Length between B and A is 1
Length between B and E is 3
Length between B and C is 1
Length between B and D is 2
Length between A and B is 1
... (and so on!)

- GeckStar

Answer 2

以下是一种查找节点之间距离的解决方案：

G = nx.Graph()
G.add_edges_from([(1,2), (1,3), (2,3), (2,4), (3,4)])
path = nx.all_pairs_shortest_path_length(G) # This is a generator
dpath = {x[0]:x[1] for x in path}           # Create a dictionary from it 
# To find e.g. the distance between node 1 and node 4: 
print(dpath[1][4]) # = 2

- Apostolos

Answer 3

根据图表的大小，您可以使用

distances = nx.floyd_warshall_numpy(graph)
nodes = np.where(distances==4)

获取距离矩阵，你可以从中筛选出符合你距离要求的内容。行和列是图中的节点 list(g)

- Sandro Martens

Answer 4

我一直在使用这个来计算最长路径 - 对于有向图来说非常困难，但对于类似树形图的图形来说却很容易。 虽然你没有特别要求这个，但它可能会帮助其他人。 顺便说一下，对于大型网络，使用all_pairs_shortest_path_length是非常昂贵的。

        # Find the longest path for a tree
        # Choose a random start. (or first).
        rnd_node = choice(nodes)
        # Find distances from random node by calculating all distances
        r_dists = dict(nx.single_source_shortest_path_length(g, rnd_node))
        begins = [node for node, dist in r_dists.items() if dist == max(r_dists.values())]
        # being the longest from a random start, makes it suitable as a start to the longest path.
        begin = choice(begins)
        # Find distances from begin by calculating all distances.
        # If we want to know the actual journey, use 'single_source_shortest_path()' instead.
        s_dists = dict(nx.single_source_shortest_path_length(g, begin))
        stops = [node for node, dist in s_dists.items() if dist == max(s_dists.values())]
        dist, stop = choice(stops)

- Konchog