在图中计算多条最短路径

Question

我有一张大型（加权、有向）图表（＞100,000个节点），我想在该图表中计算大量的随机最短路径。因此，我想随机选择两个节点（假设为k次）并计算最短路径。其中一种方法是使用networkx或igraph模块，像下面这样使用for循环：

pairs=np.random.choice(np.arange(0,len(graph.nodes)), [k,2]) 
for pair in pairs:
    graph.get_shortest_paths(pair[0],pair[1], weights='weight')

这种方法是可行的，但是需要花费很长时间。特别是与为特定源节点计算所有路径相比较。实质上，在每一次迭代中，该过程会重新加载图形并从头开始进行处理。那么是否有一种方法，可以从将图形结构加载到内存中并在每次迭代中不重复进行演算中受益，而无需计算所有最短路径（这将需要太长时间，因为这些将是n *（n-1）条路径）。

换句话说，我能否以有效的方式计算出所有最短路径的随机子集？

- quant_econ_geo

---

你看过Floyd-Warshall算法吗？它可以计算所有节点到其他所有节点的最短距离。 - hnefatl

谢谢您的回复！是的，就我所了解的而言，igraph模块会在节点数量超过一定数量时自动应用Floyd-Warshall算法。但正如我所说的，这仍然需要很长时间，因此对于我的目的来说，仅计算所有最短路径的一个较小子集就足够了。 - quant_econ_geo

抱歉，刚刚查了一下。根据R包文档，igraph模块至少使用Johnson-Dijkstra算法。根据维基百科，Johnson-Dijkstra的时间复杂度为O(EV + V2 log V)，而Floyd-Warshall的时间复杂度为O(V3)。但是，忽略时间复杂度的差异，它只是需要很长时间。某种程度上，我的（天真的）问题是，是否可以从这些高效算法中受益，但仅针对所有可能节点对的子集。 - quant_econ_geo

Answer 1

据我所知，这些操作彼此独立，因此并行运行它们可能会起作用（伪代码）：

import dask

@dask.delayed
def short_path(graph, pair):
    return graph.get_shortest_paths(pair[0],pair[1], weights='weight')

pairs=np.random.choice(np.arange(0,len(graph.nodes)), [k,2]) 
results = dask.compute(*[short_path(pair) for pair in pairs])

- SultanOrazbayev