Returns the length of paths from all nodes to remaining nodes Parameters ---------- G : graph weighted graph Returns ------- result_dict : dict the length of paths from all nodes to remaining nodes Examples -------- Returns the length of paths f
(G, weight="weight")
| 48 | @only_implemented_for_UnDirected_graph |
| 49 | @hybrid("cpp_Floyd") |
| 50 | def Floyd(G, weight="weight"): |
| 51 | """Returns the length of paths from all nodes to remaining nodes |
| 52 | |
| 53 | Parameters |
| 54 | ---------- |
| 55 | G : graph |
| 56 | weighted graph |
| 57 | |
| 58 | Returns |
| 59 | ------- |
| 60 | result_dict : dict |
| 61 | the length of paths from all nodes to remaining nodes |
| 62 | |
| 63 | Examples |
| 64 | -------- |
| 65 | Returns the length of paths from all nodes to remaining nodes |
| 66 | |
| 67 | >>> Floyd(G,weight="weight") |
| 68 | |
| 69 | """ |
| 70 | adj = G.adj.copy() |
| 71 | result_dict = {} |
| 72 | for i in G: |
| 73 | result_dict[i] = {} |
| 74 | for i in G: |
| 75 | temp_key = adj[i].keys() |
| 76 | for j in G: |
| 77 | if j in temp_key: |
| 78 | result_dict[i][j] = adj[i][j].get(weight, 1) |
| 79 | else: |
| 80 | result_dict[i][j] = float("inf") |
| 81 | if i == j: |
| 82 | result_dict[i][i] = 0 |
| 83 | for k in G: |
| 84 | for i in G: |
| 85 | for j in G: |
| 86 | temp = result_dict[i][k] + result_dict[k][j] |
| 87 | if result_dict[i][j] > temp: |
| 88 | result_dict[i][j] = temp |
| 89 | return result_dict |
| 90 | |
| 91 | |
| 92 | @not_implemented_for("multigraph") |