Compute All‑Pairs Shortest Paths on Dense Weighted Graphs with NetworkX’s floyd_warshall_numpy

Desired Outcome

Obtain a dictionary of dictionaries that maps every source node to every target node with the shortest‑path length between them for a dense weighted graph that can contain several thousand nodes. The result should be ready for downstream analytics, such as clustering or centrality calculations.

Prerequisites

• Python 3.9+ (recommended)
• NetworkX ≥ 2.6 (the floyd_warshall_numpy function was added in 2.6)
• NumPy 1.18+ (provides the array backend)
• Graph must be an instance of nx.Graph or nx.DiGraph with numeric weight attributes on edges. Missing weights default to 1.
• No negative cycles; negative edge weights are allowed but will raise NetworkXError if a cycle sums to a negative value.

Procedure

1. Import libraries

   import networkx as nx
   import numpy as np
   

2. Build or load your graph

   # Example: a small dense graph
   G = nx.Graph()
   G.add_weighted_edges_from([
       (0, 1, 2.5),
       (0, 2, 1.0),
       (1, 2, 3.0),
       (1, 3, 0.5),
       (2, 3, 4.0)
   ])
   

3. Run floyd_warshall_numpy

   dist_matrix, node_index = nx.floyd_warshall_numpy(G, weight='weight')
   # dist_matrix is a NumPy 2‑D array of shape (n, n)
   # node_index maps node to its row/column index
   

4. Convert to a dictionary of dictionaries (optional but convenient)

   nodes = list(G.nodes())
   shortest_paths = {
       u: {v: dist_matrix[i, j] for j, v in enumerate(nodes)}
       for i, u in enumerate(nodes)
   }
   

5. Save or pass the result to downstream code

Expected Checks

• Check array shape: dist_matrix.shape == (len(G), len(G))
• Verify no np.inf values unless you intentionally allow disconnected components.

  if np.isinf(dist_matrix).any():
      print('Graph has disconnected nodes')
  

• Cross‑validate a few entries with nx.dijkstra_path_length.

  for _ in range(5):
      u, v = np.random.choice(G.nodes(), 2, replace=False)
      expected = nx.dijkstra_path_length(G, u, v, weight='weight')
      actual = dist_matrix[node_index[u], node_index[v]]
      assert abs(expected - actual) < 1e-8
  

• Print the first few rows of dist_matrix to manually inspect values.

  print(dist_matrix[:5, :5])
  

Recovery Options

• Memory constraints: floyd_warshall_numpy uses O(n²) memory. If you hit a MemoryError on a graph with >10 000 nodes, switch to a sparse algorithm:

  from collections import defaultdict
  shortest_paths = defaultdict(dict)
  for source in G.nodes():
      lengths = nx.single_source_dijkstra_path_length(G, source, weight='weight')
      shortest_paths[source] = lengths
  

• Negative cycles: If NetworkXError: Negative cycle detected occurs, run nx.find_negative_cycle(G, weight='weight') (available in newer releases) to locate and remediate the cycle before re‑running.
• Smaller graphs or debugging: For graphs <1 000 nodes or when you need verbose tracing, use the pure‑Python nx.floyd_warshall which is slower but does not require NumPy and provides a dictionary of dictionaries directly.

Limitations & Practical Tips

• Because the function returns a NumPy array, the node order is determined by G.nodes(). If your graph’s nodes are not integers, the array indices will still map to the original nodes via the node_index dictionary returned by the function.
• Negative edge weights are allowed, but any negative cycle will cause the function to raise NetworkXError. Verify the graph is acyclic or remove negative edges before calling.
• For very dense graphs, the memory footprint can become prohibitive. Profile with tracemalloc or psutil.Process().memory_info() before running the algorithm on production data.
• Always verify the NetworkX version: print(nx.__version__). The floyd_warshall_numpy helper is only available in 2.6 and later.

Concrete Example: 4‑Node Graph

Below is a complete script that builds a 4‑node dense graph, runs the algorithm, and prints the resulting dictionary. The expected shortest‑path lengths are calculated manually.

import networkx as nx
import numpy as np

G = nx.Graph()
G.add_weighted_edges_from([
    (0, 1, 2.5),
    (0, 2, 1.0),
    (1, 2, 3.0),
    (1, 3, 0.5),
    (2, 3, 4.0)
])

# Run floyd‑warshall with NumPy
D, idx = nx.floyd_warshall_numpy(G, weight='weight')

# Convert to dict-of-dicts
nodes = list(G.nodes())
shortest = {u: {v: D[idx[u], idx[v]] for v in nodes} for u in nodes}

print(shortest)
# Expected output:
# {
#   0: {0: 0.0, 1: 2.5, 2: 1.0, 3: 3.0},
#   1: {0: 2.5, 1: 0.0, 2: 3.0, 3: 0.5},
#   2: {0: 1.0, 1: 3.0, 2: 0.0, 3: 4.0},
#   3: {0: 3.0, 1: 0.5, 2: 4.0, 3: 0.0}
# }

Running nx.dijkstra_path_length(G, 0, 3, weight='weight') returns 3.0, matching the entry shortest[0][3] above.

Conclusion

Using nx.floyd_warshall_numpy gives a fast, NumPy‑backed route to all‑pairs shortest‑path lengths on dense weighted graphs. By following the outlined checks and fallback strategies, you can reliably integrate this function into production pipelines while guarding against memory limits, negative cycles, and data type issues.