如何在Python中高效将边列表转换为距离矩阵？

问题背景 #

作为从R转Python的开发者，我需要处理一个包含约30000个节点、40000条边的无向无权边列表，目标是生成30000×30000的全节点最短路径距离矩阵。

在i7 16GB RAM设备上，使用R 4.3.2的igraph库仅需59秒即可完成：

library(igraph)
g <- graph_from_data_frame(el, directed = F)
dm <- distances(g)

但使用Python 3.12.4（Spyder 5.5.1）的两种NetworkX实现方式运行10分钟仍未结束：

import networkx as nx
import pandas as pd
g = nx.from_pandas_edgelist(el, 'mid', 'cid')
# Attempt 1
dm = nx.floyd_warshall_numpy(g)
# Attempt 2
gdict= dict(nx.all_pairs_shortest_path_length(g))
dm = pd.DataFrame(gdict)

其中el为pandas DataFrame，mid与cid列为uint16类型。

示例数据：

data = {
    'mid': [1, 1, 2, 2, 3, 4],
    'cid': [2, 3, 3, 4, 5, 5]
}
el = pd.DataFrame(data)

问题原因分析 #

1. 底层实现差异：R的igraph核心是C/C++编写的，而NetworkX是纯Python实现的图库，底层执行效率存在数量级差距。
2. 算法选择不当：
   • nx.floyd_warshall_numpy采用Floyd-Warshall算法，时间复杂度为O(n³)，对于30000节点的场景完全不适用；而R的igraph默认对无权图使用多源BFS算法，更适合稀疏图。
   • nx.all_pairs_shortest_path_length是纯Python循环执行单源BFS，Python的循环和函数调用开销远高于igraph的底层C实现。

高效实现方案 #

1. 使用python-igraph（igraph的Python绑定） #

直接复用igraph的C核心实现，逻辑与R代码一致，效率接近：

import igraph as ig
import pandas as pd
import numpy as np

# 从DataFrame构建无向图
g = ig.Graph.DataFrame(el, directed=False)
# 计算全节点最短路径距离
distance_matrix = g.distances()
# 转换为numpy数组或DataFrame（按需选择）
dm_np = np.array(distance_matrix)
dm_df = pd.DataFrame(dm_np, index=g.vs["name"], columns=g.vs["name"])

2. 使用SciPy稀疏图工具 #

SciPy的scipy.sparse.csgraph模块提供了C实现的最短路径算法，适合稀疏图场景：

import scipy.sparse as sp
from scipy.sparse.csgraph import shortest_path
import pandas as pd
import numpy as np

# 构建映射：节点ID到矩阵索引
all_nodes = pd.concat([el['mid'], el['cid']]).unique()
node_idx_map = {node: idx for idx, node in enumerate(all_nodes)}

# 转换边列表为稀疏邻接矩阵
rows = el['mid'].map(node_idx_map).values
cols = el['cid'].map(node_idx_map).values
data = np.ones(len(el), dtype=int)
# 无向图需构建对称邻接矩阵
adj_matrix = sp.coo_matrix((data, (rows, cols)), shape=(len(all_nodes), len(all_nodes)))
adj_matrix = adj_matrix + adj_matrix.T

# 用BFS算法计算无权图最短路径
distance_matrix = shortest_path(adj_matrix, method='BFS')
# 转换为DataFrame
dm_df = pd.DataFrame(distance_matrix, index=all_nodes, columns=all_nodes)

总结 #

并非操作有误，而是NetworkX的纯Python实现与igraph的C核心底层效率差距显著。通过切换到python-igraph或SciPy的csgraph模块，即可达到与R相近的计算速度。

内容的提问来源于stack exchange，提问作者EmilA