Single source shortest Path

graph-tool
1

Hi,

given a vertex v, I want compute all shortest paths starting at v, i.e.,
I want a list of edge or vertex lists, or some kind of DAG. Of course
this can be easily solved by Dijkstra's Algorithm, but Graph-Tools
doesn't seem to provide the right interface for this problem.

Any ideas?

Best regards,
Chris

2

Okay, I'm sorry, seems to be solved by dijkstra_search(...).

attachment.html (1.77 KB)

3

Hi,

A much faster way is to use shortest_distance() to return a predecessor
map:

   dist, pred = shortest_distance(g, source=v, pred_map=True)

The "pred" map contains for each vertex reachable from v the predecessor
node in the BFS (or Dijkstra if weighted) tree.

Best,
Tiago

4

Hi,

thank you very much. Is it somehow possible to obtain a successor
relation instead of a predecessor relation?

Best regards,
Chris

attachment.html (2.54 KB)

5

You can convert the predecessor map into a tree using
predecessor_tree(), and then you can traverse it in any way you want:

    http://graph-tool.skewed.de/static/doc/generation.html#graph_tool.generation.predecessor_tree

Best,
Tiago

6

Thanks, is it also possible to obtain the leaves of the resulting tree
without traversing the whole tree?

Best regards,
Chris

attachment.html (1.56 KB)

7

The leaves are just the nodes that are visited last by the BFS/Dijkstra,
i.e. the ones that are furthest away from the source. Are you sure this
is what you want? In any case, the answer is no, you have to find them
in the tree.

Note however that the ordering of the nodes in this tree are the same as
in the original graph. So if you want to traverse the
successor/predecessor of any particular node v in the original graph,
you can lookup t.vertex(v) in time O(1), where t is the predecessor
tree.

Best,
Tiago