Revision history [back]

Using method shortest_path_all_pairs (check the documentation of the method)

sage: G = Graph([(1, 2, 6), (1, 3, 2), (1, 4, 2), (2, 3, 1), (2, 4, 5), (3, 4, 3)])
sage: G.shortest_path_all_pairs()
({1: {1: 0, 2: 1, 3: 1, 4: 1},
  2: {1: 1, 2: 0, 3: 1, 4: 1},
  3: {1: 1, 2: 1, 3: 0, 4: 1},
  4: {1: 1, 2: 1, 3: 1, 4: 0}},
 {1: {1: None, 2: 1, 3: 1, 4: 1},
  2: {1: 2, 2: None, 3: 2, 4: 2},
  3: {1: 3, 2: 3, 3: None, 4: 3},
  4: {1: 4, 2: 4, 3: 4, 4: None}})
sage: G.shortest_path_all_pairs(by_weight=True)
({1: {1: 0, 2: 3, 3: 2, 4: 2},
  2: {1: 3, 2: 0, 3: 1, 4: 4},
  3: {1: 2, 2: 1, 3: 0, 4: 3},
  4: {1: 2, 2: 4, 3: 3, 4: 0}},
 {1: {1: None, 2: 3, 3: 1, 4: 1},
  2: {1: 3, 2: None, 3: 2, 4: 3},
  3: {1: 3, 2: 3, 3: None, 4: 3},
  4: {1: 4, 2: 3, 3: 4, 4: None}})

The first dictionary is the shortest path distance. The second is a predecessor array. We can recover the paths from it.