使用 python 的图形工具计算最短路径和距离的有效方法

Question

我有一个表示起点和终点顶点的字典，例如：

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

键表示原点（或源）顶点，值表示每个原点的目的地。 我需要计算该键的值中每个键和每个顶点之间的最短路径和距离。

比如以顶点3为原点，我需要计算3->0, 3->1 and 3->2.

之间的最短路径和距离

截至目前，我正在使用图形工具 shortest_path and shortest_distance 方法通过嵌套 for 循环实现此目的，但我相信必须有更有效的方法来实现此目的。

我还尝试通过遍历 shortest_path 返回的边来获取 shortest_distance，但是当 shortest_distance 方法接受目的地列表时，shortest_path没有。

Answer 1

我明白了。通过在 shortest_distance 中设置 pred_map=True，您将获得一个可用作 shortest_path 参数的前置映射，从而避免重新计算路径。