查找 NetworkX 中两个节点之间的所有最短路径
Finding all shortest paths between two nodes in NetworkX
假设我有一个包含 N 个节点的 BA 网络，其中每个节点至少有 2 条边。网络未加权。我正在尝试为网络中的所有节点找到每个节点 i 和 j 之间的所有最短路径。但是如果节点 i 和 j 之间有超过 1 条最短路径，那么我需要 i 和 j.
之间的每条最短路径
因此，如果可以使用路径 [0,1,2], [0,3,4,2], [0,3,4,5,2], [0,4,5,2] 和 [0,3,2] 从 0 到达节点 2，我需要一个显示 [[0,1,2], [0,3,2]].
的列表
这样做的唯一方法是计算从 i 到 j 的每条路径并获得最小长度列表吗？能否以更有效的方式建立？
编辑：显然有一种名为 all_shortest_paths 的寻路方法。我会试试这个，看看它是否有效。
Floyd Warshall 算法就是您所需要的
您可以为此使用 nx.nx.all_shortest_paths：
all_shortest_paths(G, source, target, weight=None, method='dijkstra')
这允许您指定源节点和目标节点。这是一个简单的例子：
plt.figure(figsize=(6,4))
G = nx.from_edgelist([[1,2],[2,3],[7,8],[3,8],[1,8], [2,9],[9,0],[0,7]])
nx.draw(G, with_labels=True, node_color='lightgreen')
list(nx.all_shortest_paths(G, 2, 8))
# [[2, 1, 8], [2, 3, 8]]
假设我有一个包含 N 个节点的 BA 网络，其中每个节点至少有 2 条边。网络未加权。我正在尝试为网络中的所有节点找到每个节点 i 和 j 之间的所有最短路径。但是如果节点 i 和 j 之间有超过 1 条最短路径，那么我需要 i 和 j.
因此，如果可以使用路径 [0,1,2], [0,3,4,2], [0,3,4,5,2], [0,4,5,2] 和 [0,3,2] 从 0 到达节点 2，我需要一个显示 [[0,1,2], [0,3,2]].
这样做的唯一方法是计算从 i 到 j 的每条路径并获得最小长度列表吗？能否以更有效的方式建立？
编辑：显然有一种名为 all_shortest_paths 的寻路方法。我会试试这个，看看它是否有效。
Floyd Warshall 算法就是您所需要的
您可以为此使用 nx.nx.all_shortest_paths：
all_shortest_paths(G, source, target, weight=None, method='dijkstra')
这允许您指定源节点和目标节点。这是一个简单的例子：
plt.figure(figsize=(6,4))
G = nx.from_edgelist([[1,2],[2,3],[7,8],[3,8],[1,8], [2,9],[9,0],[0,7]])
nx.draw(G, with_labels=True, node_color='lightgreen')
list(nx.all_shortest_paths(G, 2, 8))
# [[2, 1, 8], [2, 3, 8]]