我在Python 3中使用floyd_warshall_predecessor_and_distanceNetworkx函数来查找双向图上的最短路径。该函数返回给定两个节点(如果存在边)和路径的一部分之间的最短距离。我将澄清我所说的"一部分"是什么意思。以下是我的输入和输出。
输入：
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
np.random.seed(0)
V = [1, 2, 3, 4, 5]
N = [(i,j) for i in V for j in V if i!=j]
E = {} #Creating an empty dictionary to store the travel times from node i to j
Elist = (list(np.random.randint(low=1, high = 30, 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[(2, 1)] = 5
E[(5, 4)] = 0
E[(2, 4)] = 20
G=nx.DiGraph()
G.add_nodes_from(V)
for i in E:
G.add_weighted_edges_from([(i[0], i[1], E[i])])
path_lengths=nx.floyd_warshall_predecessor_and_distance(G, weight='weight')
path_lengths
输出：
({1: {2: 1, 3: 4, 4: 5, 5: 1},
2: {1: 2, 3: 4, 4: 5, 5: 1},
3: {1: 3, 2: 3, 4: 5, 5: 1},
4: {1: 4, 2: 1, 3: 4, 5: 1},
5: {1: 4, 2: 5, 3: 4, 4: 5}},
{1: defaultdict(<function networkx.algorithms.shortest_paths.dense.floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda>()>,
{1: 0, 2: 13, 3: 8, 4: 1, 5: 1}),
2: defaultdict(<function networkx.algorithms.shortest_paths.dense.floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda>()>,
{2: 0, 1: 5, 3: 13, 4: 6, 5: 6}),
3: defaultdict(<function networkx.algorithms.shortest_paths.dense.floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda>()>,
{3: 0, 1: 10, 2: 20, 4: 11, 5: 11}),
4: defaultdict(<function networkx.algorithms.shortest_paths.dense.floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda>()>,
{4: 0, 1: 5, 2: 18, 3: 7, 5: 6}),
5: defaultdict(<function networkx.algorithms.shortest_paths.dense.floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda>()>,
{5: 0, 1: 5, 2: 13, 3: 7, 4: 0})})
我特意为 (2， 4) 做了一条路径，即 2> 1> 5> 4。当我查看path_lengths[0]时，我可以看到从节点 2 到 4，我停在了 5。此外，从 2 到 5，我停在 1 上。这两个告诉我完整的路线，但我希望将整个路线视为输出，例如，2: {... 4: 1, 5, ...}或{(2,4): (2,1), (1,5), (5,4)}，而不是部分查看，然后将各个部分组合在一起。Networkx 中是否有更好的软件包可以做到这一点？顺便说一下，我的双向图不涉及负权重，而且图可以很大(这就是我选择这个函数的原因)。
这是我的尝试开始：
new = path_lengths[0]
for v in V:
for d in V:
if v!=d:
if new[v][d] != v:
new[v][d] = (new[v][d],d)
elif new[v][d] == v:
new[v][d] = (v,d)
感谢您的回复！
我找到了问题的解决方案。下面的代码创建两个字典。对于paths，键表示弧，值表示最短路径需要采用的连续弧。对于shortest_distance，键表示弧，值表示最短距离。我把这个留在这里供将来参考。
输入：
def arcs(seq, n):
return [seq[max(i, 0):i + n] for i in range(-n + 1, len(seq))]
paths = {}; shortest_distance = {}
for v in V:
for d in V:
if v!=d:
path = nx.single_source_dijkstra_path(G,v)
paths[(v,d)] = path[d]
for i in paths:
paths[i] = (arcs(paths[i],2)[1:-1])
shortest_distance[(i[0],i[1])] = path_lengths[1][i[0]][i[1]]
for j in range(len(paths[i])):
paths[i][j] = tuple(paths[i][j])
for i in paths:
print(i, paths[i], shortest_distance[i])
输出：
(1, 2) [(1, 2)] 13
(1, 3) [(1, 5), (5, 4), (4, 3)] 8
(1, 4) [(1, 5), (5, 4)] 1
(1, 5) [(1, 5)] 1
(2, 1) [(2, 1)] 5
(2, 3) [(2, 1), (1, 5), (5, 4), (4, 3)] 13
(2, 4) [(2, 1), (1, 5), (5, 4)] 6
(2, 5) [(2, 1), (1, 5)] 6
(3, 1) [(3, 1)] 10
(3, 2) [(3, 2)] 20
(3, 4) [(3, 1), (1, 5), (5, 4)] 11
(3, 5) [(3, 1), (1, 5)] 11
(4, 1) [(4, 1)] 5
(4, 2) [(4, 1), (1, 2)] 18
(4, 3) [(4, 3)] 7
(4, 5) [(4, 1), (1, 5)] 6
(5, 1) [(5, 4), (4, 1)] 5
(5, 2) [(5, 2)] 13
(5, 3) [(5, 4), (4, 3)] 7
(5, 4) [(5, 4)] 0