十万节点五亿边大型无向图全源最短路径求解方案问询

问题概述 #

针对含100000个节点、50亿条边的无向加权完全图（对称邻接矩阵$A$，$A_{ij}$为边$e_{ij}$的权重），需要计算两个矩阵：

• 矩阵$L$：$L_{ij}$表示节点$i$到$j$的最短路径边数（若存在多条权重总和相同的最短路径，取边数最少的路径）
• 矩阵$W$：$W_{ij}$表示该最短路径的权重总和

传统全源最短路径算法（如Floyd-Warshall、Johnson）在该规模下耗时极长（数百天），且直接使用igraph库会面临内存爆炸问题（65000节点构建图需340GB内存），以下是针对性的优化方案。

核心优化方向 #

1. 内存优化：放弃邻接矩阵，改用高效存储 #

10万节点的邻接矩阵包含$10^{10}$个元素，即使存储为4字节浮点数也需40GB内存，加上igraph的额外存储开销，必然导致内存溢出。优化方案：

• 压缩对称存储：仅存储邻接矩阵的上三角部分，将内存占用减半至20GB左右。
• 内存映射文件：使用numpy的memmap将矩阵存储在磁盘上，按需加载部分数据，避免一次性占用全部内存。
• 邻接表替代：对于完全图，无需显式存储邻接表，可直接通过节点索引计算边权重，进一步节省内存。

2. 算法优化：避免生成路径，直接追踪目标值 #

原代码调用get_all_shortest_paths生成所有最短路径，内存和时间成本极高。改为在Dijkstra算法中同时追踪两个关键值：

• dist[]：节点到各目标节点的最短权重总和
• edge_count[]：对应最短权重下的最小路径边数

松弛逻辑调整为：

• 若通过中间节点$u$到$w$的路径权重小于当前最短权重，更新dist[w]和edge_count[w]
• 若路径权重等于当前最短权重，但边数更少，则更新edge_count[w]

3. 并行与分布式计算 #

单个节点的Dijkstra计算独立于其他节点，可通过并行化大幅缩短总耗时：

• 多进程并行：利用CPU多核，同时处理多个节点的Dijkstra计算，Python可通过multiprocessing实现。
• GPU加速：使用RAPIDS cuGraph等GPU图计算库，利用GPU的并行计算能力，将单节点Dijkstra的计算速度提升数十倍。
• 分布式框架：若单台机器无法承载，可使用Spark GraphX、Flink Gelly等分布式图计算框架，将图数据分布到多个节点集群中并行计算。

4. 硬件升级 #

• 使用TB级内存的服务器，可直接加载压缩后的邻接矩阵，避免磁盘IO开销。
• 使用SSD存储内存映射文件，降低磁盘读写延迟。

优化后示例代码 #

import numpy as np
from tqdm import tqdm
import multiprocessing as mp
import heapq

def dijkstra_single_source(v, n, adj_mmap):
    # 初始化最短距离和边数数组
    dist = np.full(n, np.inf, dtype=np.float32)
    edge_count = np.full(n, np.inf, dtype=np.int32)
    dist[v] = 0.0
    edge_count[v] = 0

    # 初始化直接边的距离和边数
    dist[:v] = adj_mmap[v, :v]
    edge_count[:v] = 1
    dist[v+1:] = adj_mmap[v, v+1:]
    edge_count[v+1:] = 1

    # 优先队列存储(当前距离, 节点)
    heap = []
    for u in range(n):
        if u != v:
            heapq.heappush(heap, (dist[u], u))

    visited = np.zeros(n, dtype=bool)
    visited[v] = True

    while heap:
        current_dist, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True

        # 遍历所有节点（完全图特性）
        for w in range(n):
            if visited[w]:
                continue
            new_dist = current_dist + adj_mmap[u, w]
            new_edge_count = edge_count[u] + 1

            if new_dist < dist[w]:
                dist[w] = new_dist
                edge_count[w] = new_edge_count
                heapq.heappush(heap, (new_dist, w))
            elif new_dist == dist[w] and new_edge_count < edge_count[w]:
                edge_count[w] = new_edge_count
                heapq.heappush(heap, (new_dist, w))

    # 返回v到v+1及之后节点的结果（利用对称性减少计算）
    return dist[v+1:], edge_count[v+1:]

def all_pairs_shortest(n, adj_mmap_path):
    # 加载内存映射的邻接矩阵
    adj_mmap = np.memmap(adj_mmap_path, dtype='float32', mode='r', shape=(n, n))
    W = np.zeros((n, n), dtype=np.float32)
    L = np.zeros((n, n), dtype=np.int32)

    # 启动多进程池，根据CPU核心数设置进程数
    pool = mp.Pool(processes=mp.cpu_count())
    results = []

    for v in range(n):
        results.append(pool.apply_async(dijkstra_single_source, args=(v, n, adj_mmap)))

    pool.close()
    pool.join()

    # 收集结果并填充矩阵
    for v in tqdm(range(n)):
        dist_part, edge_part = results[v].get()
        W[v, v+1:] = dist_part
        L[v, v+1:] = edge_part

    # 对称填充矩阵
    W += W.T
    L += L.T
    np.fill_diagonal(W, 0.0)
    np.fill_diagonal(L, 0)

    return W, L

if __name__ == '__main__':
    test_N = 100000
    # 生成对称邻接矩阵并保存为内存映射文件
    adj = np.random.randint(1, 101, size=(test_N, test_N), dtype='int32')
    adj = np.triu(adj, k=1)  # 取上三角
    adj = adj + adj.T        # 对称填充
    np.fill_diagonal(adj, 0)
    adj = adj.astype('float32')

    adj_mmap_path = 'adjacency_matrix.dat'
    adj.tofile(adj_mmap_path)

    # 计算全源最短路径
    W, L = all_pairs_shortest(test_N, adj_mmap_path)

    # 保存结果
    W.tofile('W_matrix.dat')
    L.tofile('L_matrix.dat')

总结 #

10万节点的完全图全源最短路径计算属于超大规模图计算问题，需结合算法优化、并行计算、硬件升级三类手段才能在合理时间内完成：

• 若有GPU资源，优先选择cuGraph等GPU加速库，可将计算时间压缩至数天内。
• 若无GPU，多进程并行+内存映射可将时间从数百天缩短至数十天。
• 若单台机器无法承载，分布式图计算框架是最优选择。

内容的提问来源于stack exchange，提问作者Chibing.Xiang