Sum the weights along each shortest path among all nodes

Question

Given a weighted edgelist (node1 node2 weight). I am attempting to compute the sums of the weights along all the shortest path lengths among nodes.

I can find the shortest paths with NetworkX's all_pairs_Dykstra algorithm. But, I can't see a way to compute for each such path the sum of the weights along it. Here is my data: 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)

Here is the output I get:

0 {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]})} 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]})}

How can I compute the sums of the weights along the shortest paths? ​

Answer 1

This already gives what you are looking for

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

The output is the path to the other node and the sum of weights. Converting this information is not straightforward but possible.

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]