使用 Networkx 在 Python 中使用 Floyd-Warshall 算法查找最短路径

Question

我是 Networkx 软件包的新手。我在 V 中有以下顶点并在 N 中创建了边。然后，我随机分配了一些数字来表示边距离并创建了字典 E 来存储边和距离信息。我想通过使用 Floyd-Warshall 算法找到每对节点的最短路径。我搜索了一些示例，但最终没有找到我可以轻松实现的示例。所以，我开始学习如何使用 "networkx" 包创建图表。

import networkx as nx
import numpy as np
np.random.seed(0)
V = [333092, 467979, 177073, 164786, 178581]
N = [(i,j) for i in V for j in V if i!=j]
E = {}
Elist = list(np.random.randint(low=10, high = 50, size = len(N)))
for i in range(len(N)):
    E[N[i]] = Elist[i] # (i,j) does not have to be equal to (j,i)

这是图形的代码，缺少应用程序尝试寻找最短路径。我知道我从来没有使用过字典 E，所以我不应该期待一个正确的解决方案。但是，我只是不明白如何输入 nx.floyd_warshall().

G=nx.Graph()
G.add_nodes_from(V)
for i in range(len(N)):
    G.add_edge(N[i][0], N[i][1])
nx.floyd_warshall(G)

Answer 1

您似乎正确地输入了 nx.floyd_warshall（至少将图形视为未加权），但我怀疑您可能想知道如何处理权重。这是一个示例，其中我为每条边赋予了一个随机权重，其键为 'distance'.

import networkx as nx
import numpy as np
import random
np.random.seed(0)
V = [333092, 467979, 177073, 164786, 178581]
N = [(i,j) for i in V for j in V if i!=j]
G=nx.Graph()
G.add_nodes_from(V)
for i in range(len(N)):
    G.add_edge(N[i][0], N[i][1], distance = random.random())
path_lengths=nx.floyd_warshall(G, weight='distance')
print(path_lengths[333092][467979])
>0.5257894083921129

path_lengths（我命名为 nx.floyd_warshall 的结果）基本上是字典的字典。 path_lengths[u][v]是从u到v的最短路径长度。

请注意 weight 的默认值为 weight='weight'，因此如果定义了该键，除非您另有说明，否则将使用它。如果未定义权重，则将每条边视为权重 1。

使用 Networkx 在 Python 中使用 Floyd-Warshall 算法查找最短路径

Finding Shortest Path with Floyd-Warshall Algorithm in Python using Networkx

graph

shortest-path

networkx

python-3.x

floyd-warshall