CODEWITHSUNDEEP
pythongraphshortest-pathgraph-tool
megalodon
megalodon

Reputation: 63

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

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.

Upvotes: 2

Views: 579

Answers (1)

megalodon
megalodon

Reputation: 63

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.

Upvotes: 3

Related Questions