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

efficient way of calculating shortest path and distance with python's graph-tool

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

I have a dictionary representing origin and destination vertices, for example:

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

The keys represent origin (or source) vertices and the values represent destinations for each origin vertex. I need to calculate the shortest path and distance between every key and each vertex in the value for that key.

For example, with vertex 3 as the origin, I need to calculate the shortest path and distance between 3->0, 3->1 and 3->2.

As of now, I'm achieving this with a nested for loop, using graph-tools shortest_path and shortest_distance methods, but I believe there must be a more efficient way to achieve this.

I also tried to get the shortest_distance by iterating through the edges returned by shortest_path, but while the shortest_distance method accepts a list of destinations, the shortest_path does not.

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

I figured it out. By setting pred_map=True in shortest_distance, you get a predecessor map that can be used as an argument to shortest_path, thus avoiding recomputing the path.