グラフの枝(i,j)を最短経路に含むODペアの集合

Question

pyhonで以下の写真の集合S_{ij}のプログラムの仕方がわかりません。
ワーシャルフロイド法を使って最短経路、最短距離を求めて手詰まりになりました。
大分いい加減な質問になっていしまいましたが、教えていただけると幸いです。

war = nx.floyd_warshall_numpy(G)
print('最短経路の長さ')
print(war)
print('最短経路')
warshall=nx.floyd_warshall_predecessor_and_distance(G)
print(warshall)

#実行結果
#最短距離の長さ（war）
[[ 0.          6.32455532  4.          5.         14.38681307  9.
  13.         18.85730076 13.47213595]
 [ 6.32455532  0.          6.32455532 10.44766095  8.06225775 11.32455532
  15.79669128 14.46538199 15.79669128]
 [ 4.          6.32455532  0.          4.12310563 12.07106781  5.
   9.47213595 14.85730076  9.47213595]
 [ 5.         10.44766095  4.12310563  0.         16.19417344  9.12310563
   8.         16.21359193 10.82842712]
 [14.38681307  8.06225775 12.07106781 16.19417344  0.          7.07106781
  11.54320377  6.40312424 11.54320377]
 [ 9.         11.32455532  5.          9.12310563  7.07106781  0.
   4.47213595  9.85730076  4.47213595]
 [13.         15.79669128  9.47213595  8.         11.54320377  4.47213595
   0.          8.21359193  2.82842712]
 [18.85730076 14.46538199 14.85730076 16.21359193  6.40312424  9.85730076
   8.21359193  0.          5.38516481]
 [13.47213595 15.79669128  9.47213595 10.82842712 11.54320377  4.47213595
   2.82842712  5.38516481  0.        ]]
#最短経路(warshall)
({1: {2: 1, 3: 1, 4: 1, 5: 2, 6: 3, 7: 4, 8: 9, 9: 6}, 2: {1: 2, 3: 2, 5: 2, 4: 3, 6: 3, 7: 6, 8: 5, 9: 6}, 3: {1: 3, 2: 3, 4: 3, 6: 3, 5: 6, 7: 6, 8: 9, 9: 6}, 4: {1: 4, 3: 4, 7: 4, 2: 3, 5: 6, 6: 3, 8: 9, 9: 7}, 5: {2: 5, 6: 5, 8: 5, 1: 2, 3: 6, 4: 3, 7: 6, 9: 6}, 6: {3: 6, 5: 6, 7: 6, 9: 6, 1: 3, 2: 3, 4: 3, 8: 9}, 7: {4: 7, 6: 7, 9: 7, 1: 4, 2: 3, 3: 6, 5: 6, 8: 9}, 8: {5: 8, 9: 8, 1: 3, 2: 5, 3: 6, 4: 7, 6: 9, 7: 9}, 9: {6: 9, 7: 9, 8: 9, 1: 3, 2: 3, 3: 6, 4: 7, 5: 6}}, {1: defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x000002495FE98598>, {1: 0, 2: 6.324555320336759, 3: 4.0, 4: 5.0, 5: 14.386813068635309, 6: 9.0, 7: 13.0, 8: 18.857300762134084, 9: 13.47213595499958}), 2: defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x000002495FE98620>, {2: 0, 1: 6.324555320336759, 3: 6.324555320336759, 5: 8.06225774829855, 4: 10.44766094595442, 6: 11.32455532033676, 7: 15.79669127533634, 8: 14.465381985731398, 9: 15.79669127533634}), 3: defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x000002495FE986A8>, {3: 0, 1: 4.0, 2: 6.324555320336759, 4: 4.123105625617661, 6: 5.0, 5: 12.071067811865476, 7: 9.47213595499958, 8: 14.857300762134084, 9: 9.47213595499958}), 4: defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x000002495FE98730>, {4: 0, 1: 5.0, 3: 4.123105625617661, 7: 8.0, 2: 10.44766094595442, 5: 16.194173437483137, 6: 9.123105625617661, 8: 16.213591931880693, 9: 10.82842712474619}), 5: defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x000002495FE987B8>, {5: 0, 2: 8.06225774829855, 6: 7.0710678118654755, 8: 6.4031242374328485, 1: 14.386813068635309, 3: 12.071067811865476, 4: 16.194173437483137, 7: 11.543203766865055, 9: 11.543203766865055}), 6: defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x000002495FE98840>, {6: 0, 3: 5.0, 5: 7.0710678118654755, 7: 4.47213595499958, 9: 4.47213595499958, 1: 9.0, 2: 11.32455532033676, 4: 9.123105625617661, 8: 9.857300762134084}), 7: defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x000002495FE988C8>, {7: 0, 4: 8.0, 6: 4.47213595499958, 9: 2.8284271247461903, 1: 13.0, 2: 15.79669127533634, 3: 9.47213595499958, 5: 11.543203766865055, 8: 8.213591931880694}), 8: defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x000002495FE98950>, {8: 0, 5: 6.4031242374328485, 9: 5.385164807134504, 1: 18.857300762134084, 2: 14.465381985731398, 3: 14.857300762134084, 4: 16.213591931880693, 6: 9.857300762134084, 7: 8.213591931880694}), 9: defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x000002495FE98B70>, {9: 0, 6: 4.47213595499958, 7: 2.8284271247461903, 8: 5.385164807134504, 1: 13.47213595499958, 2: 15.79669127533634, 3: 9.47213595499958, 4: 10.82842712474619, 5: 11.543203766865055})})

Answer 1

for (i,j) in pi:
    a=nx.dijkstra_path(G,i,j)
    for k in range(len(a)-1):
        S[a[k]-1][a[k+1]-1].add((i,j))

#実行結果
[
[set(), {(1, 2), (1, 5)}, {(1, 8), (1, 3), (1, 6), (1, 9)}, {(1, 4), (1, 7)}, set(), set(), set(), set(), set()], 
[set(), set(), {(2, 7), (2, 6), (2, 9), (2, 3), (2, 4)}, set(), {(2, 8), (2, 5), (1, 5)}, set(), set(), set(), set()],
[set(), set(), set(), {(3, 4), (2, 4)}, set(), {(2, 7), (2, 6), (4, 6), (2, 9), (4, 5), (3, 8), (1, 8), (3, 9), (1, 6), (1, 9), (3, 6), (3, 7), (3, 5)}, set(), set(), set()], 
[set(), set(), {(4, 5), (4, 6)}, set(), set(), set(), {(4, 7), (1, 7), (4, 9), (4, 8)}, set(), set()], 
[set(), set(), set(), set(), set(), {(5, 6), (5, 9), (5, 7)}, set(), {(2, 8), (5, 8)}, set()], 
[set(), set(), set(), set(), {(4, 5), (3, 5)}, set(), {(2, 7), (5, 9), (6, 7), (5, 7), (3, 7)}, set(), {(5, 9), (6, 9), (6, 8), (2, 9), (3, 8), (1, 8), (3, 9), (1, 9)}], 
[set(), set(), set(), set(), set(), set(), set(), set(), {(7, 8), (7, 9), (4, 9), (4, 8)}], 
[set(), set(), set(), set(), set(), set(), set(), set(), {(8, 9)}], 
[set(), set(), set(), set(), set(), set(), set(), {(6, 8), (4, 8), (3, 8), (1, 8), (7, 8)}, set()]
]