# Shortest path tree rooted at given vertex (weighted, undirected)

Do we have anything like that? All I can find is the minimum spanning tree function, which roots it wherever it wants.

I need this for the minimum cycle basis PR.

Thank you!

The minimum spanning tree function creates a new `igraph_t` object. Creating new graphs should not be necessary to find a cycle basis.

You will need to do a breadth first search. I expect `igraph_bfs` not to be a perfect fit for this use case, so I would write an appropriate version from scratch.

Just to confirm. We donâ€™t have any function that finds a shortest path tree rooted at a specific vertex right?

Iâ€™m not sure what you mean by â€śshould not be necessaryâ€ť: nothing is necessary in life except oxygen and food, but tools help keep the house tidy. Are you familiar with the algorithm Iâ€™m trying to implement?

No, there is no function that constructs a new graph (tree) which is a shortest path tree.

It will be inefficient to construct a new graph. I would not prefer an implementation that does that.

Thank you.
I agree it would be best to avoid that, however the algorithm is not trivial, not just one bfs.

If you are concerned itâ€™d be great if you could have a look at the PR and comment or, even better, implement some of those functions. Iâ€™m sure you could do some of that better than myself

To be clear, the signature for finding the minimum spanning tree function is

``````int igraph_minimum_spanning_tree(const igraph_t* graph,
igraph_vector_t* res, const igraph_vector_t* weights)
``````

In other words, it does not construct a new graph.

In fact, I donâ€™t understand why the function `igraph_minimum_spanning_tree_prim` is there, which has the signature

``````int igraph_minimum_spanning_tree_prim(const igraph_t *graph, igraph_t *mst,
const igraph_vector_t *weights)
``````

and which does not do much more than calling `igraph_minimum_spanning_tree` and then using the returned edges to build a new graph. This is trivial, and can be left to a user of `igraph`. Moreover, the naming is rather unclear, because `igraph_minimum_spanning_tree_prim` suggests it simply uses a specific algorithm, but does the same, while in reality, it does something else, namely creating a subgraph. I propose we remove `igraph_minimum_spanning_tree_prim`.

Moreover, it seems that @iosonofabio needs rooted trees that represent the shortest distance to vertices from a given vertex. In directed graphs, such trees depend on the vertex that is used as a root. To me, it would make sense to have an implementation of `igraph_minimum_spanning_tree` that allows you to indicate a root vertex (or vertices in the case of multiple components) and that works on directed graphs. Since @iosonofabio is working on that, wouldnâ€™t it make sense to also include that as a public function, instead of just an internal function?

Yes in fact I have added my first try for that function to the cycle basis PR, it just swaps vertex indices to enforce a root, happy to move it to the other file and expose it as API if you guys think it work as expected!

1 Like