尝试使用 networkx 查找两个节点之间的距离（欧几里得）

Question

关于如何计算图中两个节点之间的欧氏距离有什么建议吗？使用此图表：

nodes = [('B','D'), ('D','E'), ('D','A'), ('E','A'), ('E','C'), ('A','C')]
graph = nx.Graph(nodes)
nx.draw(graph, node_color = 'red', with_labels = True)

我试过使用

nx.shortest_path(graph, source, target)

使用 nx.shortest_path() 会出现以下错误：

TypeError: argument of type 'NoneType' is not iterable

我知道 Dijkstra 算法，但我只想计算欧氏距离。有什么建议吗？

Answer 1

您应该能够像这样计算最短距离：

dist = nx.shortest_path(graph, 'A', 'B')

dist 的长度给出了节点 A 和 B 之间的步数：

len(dist)

# returns 3

计算欧氏距离需要节点具有某种与它们相关联的坐标。

例如存储在属性中 coords:

# adding coordinates:
for n in graph.nodes:
    graph.nodes[n]['coords'] = np.random.rand(2)
    
def get_euclidean_distance(graph, source, dest):
    x1, y1 = graph.nodes[source]['coords']
    x2, y2 = graph.nodes[dest]['coords']
    
    return np.sqrt((x1-x2)**2 + (y1-y2)**2) 


get_euclidean_distance(graph, 'A', 'B')

# out 0.14540849196243125

Answer 2

我没有找到属性 'coords'，我找到的是：

graph.nodes[56407653]
{'y': 33.5077195, 'x': -86.8048775, 'street_count': 4}

所以函数可能会变成：

def get_euclidean_distance(source, dest):
    x1, y1 = graph.nodes[source]['x'], graph.nodes[source]['y']
    x2, y2 = graph.nodes[dest]['x'], graph.nodes[dest]['y']
    
    return np.sqrt((x1-x2)**2 + (y1-y2)**2)

尝试使用 networkx 查找两个节点之间的距离（欧几里得）

Trying to find the distance (Euclidean) between two nodes using networkx

graph-theory

networkx

python-3.x