计算有向图中的最短路径比计算介数中心性花费的时间要长得多

Question

首先，我尝试计算具有 N=3015 个节点的边权重的全连接有向图的介数中心性。 Matlab 可以在大约 30 秒内完成此操作，Python igraph 可以在一分钟内完成，而 Networkx 需要几个小时，因为它是用 python 编写的，所以我放弃了它。

其次，我需要获取所有节点对之间的所有最短路径（最小化沿路径权重的路径）的列表。在 matlab 中，有一个函数可以执行此操作，称为“最短路径”。 igraph 中也有一个类似的函数，称为 get_shortest_paths。每次通话我只能得到一条返回路径。 因此，我循环遍历所有 $N^2$ 对节点并提取最短路径，将其存储在数组中，然后继续。

问题是，虽然我可以在一分钟内获得介数中心性，但在 matlab 和 igraph 中提取所有最短路径都需要几个小时。

考虑到介数中心性是基于所有最短路径的计算，这似乎很奇怪。那么为什么提取最短路径需要花费如此长的时间呢？

Answer 1

get_all_shortest_paths

 而不是 

get_shortest_path。事实上，

get_shortest_path

仅返回一条最短路径，但

get_all_shortest_paths

将返回所有最短路径。

Answer 2

你可以想象，如果从 A 点和 B 点到另一个点 C 的最短路径大部分重叠，那么一定有一种方法可以重用构建从 A 到 C 的路径的知识，以快速找到 B 到 C 的路径。 ，这就是

Dijkstra 算法

（对于单源最短路径）和其他算法（例如 Floyd-Warshall 算法）（对于所有最短路径）在 igraph、in networkx 和 matlab I 之间的区别认为是距离。