Home>

python - a set of od pairs including the graph branch (i, j) in the shortest path

I don't know how to program S_ {ij} with the following set of photos in pyhon.
Using the Warsal Floyd method, the shortest path and the shortest distance were found, and it became clogged.
I'm sorry, but I would appreciate it if you could tell me.

war = nx.floyd_warshall_numpy (G)
print ('shortest path length')
print (war)
print ('shortest path')
warshall = nx.floyd_warshall_predecessor_and_distance (G)
print (warshall)
#Execution result
#Length of shortest distance (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.]]
#Shortest path (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_di.<<>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.12310 5625617661, 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>.<Lambdas ..<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: default 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.21359 1931880694}), 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 0x000002495FE9 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})})


python
  • 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))
#Execution result
[
[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 ()]
]

Related articles

Trends