"计算所有节点之间最短路径上的权重总和"

Question

给定加权边列表（node1 node2 weight）。我试图计算节点间所有最短路径长度上的权重之和。你知道吗

我可以用NetworkX的all\u pairs\u Dykstra算法找到最短路径。 但是，我找不到一种方法来计算每一条路径上的权重之和。这是我的数据：https://drive.google.com/file/d/125OVYNsGTYgnxs7HRv9Jg64bKfnn4m64/view?usp=sharingt

import networkx as nx  
G= nx.read_weighted_edgelist(r'C:\Users\james\Desktop\Documents\Downloads\testdata2.ptg', create_using= nx.DiGraph())
len(G.nodes()), len(G.edges())
nodeNums = len(G.nodes())
print(nodeNums)
#Find all shortest paths
G=nx.path_graph(5)
len_path = dict(nx.all_pairs_dijkstra(G, weight='weight'))
for node in G:
print(node,len_path)

下面是我得到的结果：

0{{0{0{0:0，1:1，1:1，2:2，3:3，3:3，3:4}，{0:[0:[0，1、1、2、2、2、3:[0，1:0、1:0、1:0、1:0、1:1、2:2、2:2、3:3、3:3、4:3}，{1:[1、0、0、2:[1、1、1、1、2、1、1、1、2、1、2、2、2、2、3）、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3、3）、3、3、3、3、3、3，4:[2，3，4]}），3:（{3:0，2:1，4:1，1:2，0:3}，{3: [3], 2: [3, 2], 4: [3, 4], 1: [3, 2, 1], 0: [3, 2, 1, 0]}), 4: ({4: 0, 3: 1, 2: 2, 1: 3, 0: 4}, {4: [4], 3: [4, 3], 2: [4, 3, 2], 1: [4, 3, 2, 1], 0: [4, 3, 2, 1, 0]})} 1 {0: ({0: 0, 1: 1, 2: 2, 3: 3, 4: 4}, {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [0, 1, 2, 3, 4]}), 1: ({1: 0, 0: 1, 2: 1, 3: 2, 4: 3}, {1: [1], 0: [1, 0], 2: [1, 2], 3: [1, 2, 3], 4: [1, 2, 3, 4]}), 2: ({2: 0, 1: 1, 3: 1, 0: 2, 4: 2}, {2: [2], 1: [2, 1], 3: [2, 3], 0: [2, 1, 0], 4: [2, 3, 4]}), 3: ({3: 0, 2: 1, 4: 1, 1: 2, 0: 3}, {3: [3], 2: [3, 2], 4: [3, 4], 1: [3, 2, 1], 0: [3, 2, 1, 0]}), 4: ({4: 0, 3: 1, 2: 2, 1: 3, 0: 4}, {4: [4], 3: [4, 3], 2: [4, 3, 2], 1: [4, 3, 2, 1], 0: [4, 3, 2, 1, 0]})} 2 {0: ({0: 0, 1: 1, 2: 2, 3: 3, 4: 4}, {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [0, 1, 2, 3, 4]}), 1: ({1: 0, 0: 1, 2: 1, 3: 2, 4: 3}, {1: [1], 0: [1, 0], 2: [1, 2], 3: [1, 2, 3], 4: [1, 2, 3, 4]}), 2: ({2: 0, 1: 1, 3: 1, 0: 2, 4: 2}, {2: [2], 1: [2, 1], 3: [2, 3], 0: [2, 1, 0], 4: [2, 3, 4]}), 3: ({3: 0, 2: 1, 4: 1, 1: 2, 0: 3}, {3: [3], 2: [3, 2], 4: [3, 4], 1: [3, 2, 1], 0: [3, 2, 1, 0]}), 4: ({4: 0, 3: 1, 2: 2, 1: 3, 0: 4}, {4: [4], 3: [4, 3], 2: [4, 3, 2], 1: [4, 3, 2, 1], 0: [4, 3, 2, 1, 0]})} 3 {0: ({0: 0, 1: 1, 2: 2, 3: 3, 4: 4}, {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [0, 1, 2, 3, 4]}), 1: ({1: 0, 0: 1, 2: 1, 3: 2, 4: 3}, {1: [1], 0: [1, 0], 2: [1, 2], 3: [1, 2, 3], 4: [1, 2, 3, 4]}), 2: ({2: 0, 1: 1, 3: 1, 0: 2, 4: 2}, {2: [2], 1: [2, 1], 3: [2, 3], 0: [2, 1, 0], 4: [2, 3, 4]}), 3: ({3: 0, 2: 1, 4: 1, 1: 2, 0: 3}, {3: [3], 2: [3, 2], 4: [3, 4], 1: [3, 2, 1], 0: [3, 2, 1, 0]}), 4: ({4: 0, 3: 1, 2: 2, 1: 3, 0: 4}, {4: [4], 3: [4, 3], 2: [4, 3, 2], 1: [4, 3, 2, 1], 0: [4, 3, 2, 1, 0]})} 4 {0: ({0: 0, 1: 1, 2: 2, 3: 3, 4: 4}, {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [0, 1, 2, 3, 4]}), 1: ({1: 0, 0: 1, 2: 1, 3: 2, 4: 3}, {1: [1], 0: [1, 0], 2: [1, 2], 3: [1, 2, 3], 4: [1, 2, 3, 4]}), 2: ({2: 0, 1: 1, 3: 1, 0: 2, 4: 2}, {2: [2], 1: [2, 1], 3: [2, 3], 0: [2, 1, 0], 4: [2, 3, 4]}), 3: ({3: 0, 2: 1, 4: 1, 1: 2, 0: 3}, {3: [3] ，2:[3，2]，4:[3，4]，1:[3，2，1]，0:[3，2，1，0]}，4:（{4:0，3:1，2:2，1:3，0:4}，{4:[4]，3:[4，3]，2:[4，3，2]，1:[4，3，2，1]，0:[4，3，2，1，0]}）

如何计算沿最短路径的权重之和？ 你知道吗

Answer 1

这已经给了你想要的

len_path = dict(nx.all_pairs_dijkstra(G, weight='weight'))

输出是到另一个节点的路径和权重之和。转换这些信息并不简单，但却是可能的。你知道吗

import networkx as nx 
import pandas as pd 
G= nx.read_weighted_edgelist('/Users/ybaktir/Downloads/testdata2.ptg', create_using= nx.DiGraph())
len_path = dict(nx.all_pairs_dijkstra(G, weight='weight'))

nodes = list(G.nodes())
results = pd.DataFrame()

starting_point = []
for i in range(len(nodes)):
    results = results.append(pd.DataFrame(len_path[nodes[i]]).T.reset_index())
    starting_point = starting_point + [nodes[i]]*len(len_path[nodes[i]][1])


paths_df = pd.DataFrame()
paths_df['starting_point'] = starting_point

results.columns = ['ending_point','weight','path']
results = results.reset_index()
del results['index']

results = pd.concat((paths_df,results),axis=1)

print(results)
   starting_point ending_point weight       path
0               1            1      0        [1]
1               1            2    100     [1, 2]
2               1            4    200     [1, 4]
3               1            3    300  [1, 2, 3]
4               1            5    350  [1, 2, 5]
5               2            2      0        [2]
6               2            3    200     [2, 3]
7               2            5    250     [2, 5]
8               4            4      0        [4]
9               4            5    700     [4, 5]
10              5            5      0        [5]
11              3            3      0        [3]