# Longest path in a weighted DAG

**URL:** <https://igraph.discourse.group/t/longest-path-in-a-weighted-dag/149>\
**Category:** Usage\
**Tags:** R\
**Created:** [24 March 2020 08:23 UTC](https://igraph.discourse.group/t/longest-path-in-a-weighted-dag/149 "2020-03-24T08:23:48Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Jakob](https://avatars.discourse-cdn.com/v4/letter/j/71c47a/32.png) [@Jakob](https://igraph.discourse.group/u/Jakob)\
**Post date:** [24 March 2020 08:23 UTC](https://igraph.discourse.group/t/longest-path-in-a-weighted-dag/149/1 "2020-03-24T08:23:48Z")

</div>

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](https://igraph.org/c/doc/igraph-Structural.html#igraph_shortest_paths_johnson) 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

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [27 March 2020 20:19 UTC](https://igraph.discourse.group/t/longest-path-in-a-weighted-dag/149/2 "2020-03-27T20:19:32Z")

</div>

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 …

---

<div class="post-metadata">

**Author:** ![Emanuel\_Lima](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/emanuel_lima/32/306_2.png) [@Emanuel\_Lima](https://igraph.discourse.group/u/Emanuel_Lima)\
**Post date:** [16 July 2020 16:49 UTC](https://igraph.discourse.group/t/longest-path-in-a-weighted-dag/149/3 "2020-07-16T16:49:04Z")

</div>

Hi Jakob,

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

Thanks in advance,  
Emanuel

---

<div class="post-metadata">

**Author:** ![Jakob](https://avatars.discourse-cdn.com/v4/letter/j/71c47a/32.png) [@Jakob](https://igraph.discourse.group/u/Jakob)\
**Post date:** [31 July 2020 07:16 UTC](https://igraph.discourse.group/t/longest-path-in-a-weighted-dag/149/4 "2020-07-31T07:16:01Z")

</div>

Hi Emanuel,

I opened a GitHub [issue](https://github.com/igraph/rigraph/issues/386) and there has been a bit of a discussion on `shortest.paths()` vs `shortest_paths()` but no solution for the original problem so far.

---

<div class="post-metadata">

**Author:** ![Emanuel\_Lima](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/emanuel_lima/32/306_2.png) [@Emanuel\_Lima](https://igraph.discourse.group/u/Emanuel_Lima)\
**Post date:** [31 July 2020 07:54 UTC](https://igraph.discourse.group/t/longest-path-in-a-weighted-dag/149/5 "2020-07-31T07:54:08Z")

</div>

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 🙂

cheers