Warm tip: This article is reproduced from serverfault.com, please click

其他-使用python的graph-tool计算最短路径和距离的有效方法

(其他 - efficient way of calculating shortest path and distance with python's graph-tool)

发布于 2020-11-29 18:10:52

我有一本代表起点和终点的字典,例如:

{
    0: [1,3],
    1: [0,2],
    2: [1],
    3: [0,1,2],
}

键代表原点(或源)顶点,值代表每个原点的目的地。我需要计算该键的值中每个键与每个顶点之间的最短路径和距离。

例如,以顶点3为原点,我需要计算之间的最短路径和距离3->0, 3->1 and 3->2

到目前为止,我已经使用图形工具shortest_pathshortest_distance方法通过嵌套的for循环实现了这一目标,但我相信必须有一种更有效的方法来实现这一目标。

我还尝试通过遍历所返回的边缘来获取shortest_distance shortest_path,但是尽管该shortest_distance方法接受目标列表,但shortest_path并不能。

Questioner
megalodon
Viewed
0
megalodon 2020-12-01 22:21:48

我想到了。通过设置pred_map=Trueshortest_distance,你可以用来作为参数传递给前任 mapshortest_path,从而避免重新计算路径。