Longest path in a weighted DAG

Usage
1

Hi,

i would like to get the longest path(s) in a weighted directed acylcical graph in R. In principle, I would just negate the weights and then get the shortest paths. However, the algorithms for dealing with negative weights (Bellman-Ford and Johnson) are only available for the distances() function but not for the shortest_paths() or all_shortest_paths() functions.

It seems these functions are available in the C library but I don’t know how to expose them to R.
Would it be possible to make the additional algorithms available for the shortest path functions in R? Or could someone point me towards how I could use the C functions directly from R?

Best and thanks
Jakob

2

It may not be a bad idea to open an issue for R/igraph on GitHub and request adding this.

Sorry, I’m not very experienced with R, and much less so with calling C from R, so I can’t answer …

3

Hi Jakob,

I am exactly with the same problem. Can you please share with me what was your solution?

Thanks in advance,
Emanuel

4

Hi Emanuel,

I opened a GitHub issue and there has been a bit of a discussion on shortest.paths() vs shortest_paths() but no solution for the original problem so far.

5

Hi Jakob,

Thanks for the answer.
Since I am only working with a DAG with positive weights I just converted the weights to negative and use the Bellman-Ford to compute the cost from the source to each vertex. Then I implemented my own function in R to extract the path using that information.
The code is not very efficient but I think it will be enough :slight_smile:

cheers