有向图全最短路径提取耗时为何远超介数中心性计算？

• 介数中心性的高效计算：Brandes算法的核心优化
  介数中心性确实基于所有节点对的最短路径计算，但Matlab、igraph这类工具采用的Brandes算法，根本不需要显式枚举或存储所有最短路径：

  1. 对每个源节点，仅执行一次Dijkstra（带权图）或BFS（无权图），同时计算所有节点的最短距离，记录每个节点的前驱节点集合（即哪些节点能通过最短路径到达当前节点）。
  2. 从目标节点反向回溯到源节点，用动态规划方式计算每个节点在最短路径上的“流量贡献”——也就是统计有多少条最短路径会经过该节点，直接把这个数值累积到介数结果中。
  3. 整个过程只维护距离、前驱集合和临时流量计数，完全跳过了路径的实际提取与存储步骤，时间复杂度控制在$O(N(M + N \log N))$（带权图），这就是它能在几十秒内完成3015节点计算的原因。

• 直接提取全最短路径的耗时瓶颈
  当你遍历所有$N^2$节点对调用get_shortest_paths或Matlab最短路径函数时，会遇到几个无法避开的开销：

  1. 重复计算：默认每次调用函数都会单独执行一次最短路径搜索，而Brandes算法对每个源节点只跑一次搜索，就能覆盖所有目标节点的路径贡献，避免了数百万次重复计算。
  2. 路径枚举与存储：如果节点对存在大量最短路径（比如全连接带权图中，可能存在多条权重相同的路径），工具需要把每条路径的节点序列都提取出来存储，这不仅占用海量内存，枚举路径的过程本身就是指数级的时间消耗——远超过统计流量贡献的成本。
  3. 函数调用开销：遍历近900万次（3015²）节点对时，每次函数调用的参数传递、初始化等额外开销会被无限放大，累积起来就是数小时的耗时。

• 针对你场景的补充说明
  你可以验证：igraph的betweenness函数本质是用Brandes算法在单次源节点遍历中完成所有路径贡献统计，完全不生成实际路径。哪怕你优化调用方式（比如对每个源节点一次性获取所有目标节点的前驱集合，再自行回溯生成路径），时间开销依然会远高于介数计算——因为路径的生成、存储成本是无法绕过的。

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