# computation time of distances() significantly increases with edge weights?!

**URL:** <https://igraph.discourse.group/t/computation-time-of-distances-significantly-increases-with-edge-weights/1424>\
**Category:** Usage\
**Tags:** C, R\
**Created:** [26 November 2022 14:11 UTC](https://igraph.discourse.group/t/computation-time-of-distances-significantly-increases-with-edge-weights/1424 "2022-11-26T14:11:58Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![itati01](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/itati01/32/882_2.png) [@itati01](https://igraph.discourse.group/u/itati01)\
**Post date:** [26 November 2022 14:11 UTC](https://igraph.discourse.group/t/computation-time-of-distances-significantly-increases-with-edge-weights/1424/1 "2022-11-26T14:11:58Z")

</div>

Hi,

I am new to igraph and this forum. So, hopefully, this is the right place to report or clarify my issue. I use igraph with R but as it is likely related to the underlying C code, I tagged it with R and C.

In order to calculate the maximum distance of vertices to the root(s) of a graph, I apply `igraph::distances()` and an edge weight of -1. The computation time more than doubles compared to distances without any weight. For me, such a difference is quite surprising but may be there is an explanation. There is no difference between weight=-1 and weight=1.

Thanks,  
Andreas

Example code (note: in this case the output should not depend on the weight)

```auto
# dag with 10000 edges
kk <- data.frame(from=seq(10000))
kk$to <- kk$from+1
g <- igraph::graph_from_data_frame(kk)
inlets <- igraph::degree(g, mode="in")
inlets <- inlets[inlets==0]
g.1 <- igraph::set.edge.attribute(g, name="weight", value=-1)
# only for comparison: the weight value has no impact
g.2 <- igraph::set.edge.attribute(g, name="weight", value=1)
# without weight, make sure we use the same algorithm
# note: I do not use the algorithm argument
microbenchmark::microbenchmark({mm <- igraph::distances(g, mode="in", to=names(inlets), algorithm="bellman-ford")}, times=3)
microbenchmark::microbenchmark({mm <- -igraph::distances(g.1, mode="in", to=names(inlets), algorithm="bellman-ford")}, times=3)
microbenchmark::microbenchmark({mm <- igraph::distances(g.2, mode="in", to=names(inlets), algorithm="bellman-ford")}, times=3)
# next steps
# mm[is.infinite(mm)] <- -1
# res <- apply(mm, 1, max)

```

---

<div class="post-metadata">

**Author:** ![GroteGnoom](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/grotegnoom/32/428_2.png) [@GroteGnoom](https://igraph.discourse.group/u/GroteGnoom)\
**Post date:** [26 November 2022 17:40 UTC](https://igraph.discourse.group/t/computation-time-of-distances-significantly-increases-with-edge-weights/1424/2 "2022-11-26T17:40:08Z")

</div>

I think when you don’t have negative edges, the work is passed on to Dijkstra’s algorithm, because it’s faster.

---

<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:** [26 November 2022 18:35 UTC](https://igraph.discourse.group/t/computation-time-of-distances-significantly-increases-with-edge-weights/1424/3 "2022-11-26T18:35:15Z")

</div>

This is expected. Different algorithms are used for:

1. The unweighted case (simple breadth-first search).
2. Weighted graph with non-negative weights (Dijkstra’s algorithm).
3. Weighted graph with some negative weights (Bellman–Ford algorithm).

This is true even if you set the `algorithm` parameter.

(1) will be faster (has better complexity) than (2) or (3). You can look up the complexities of these algorithms in the C/igraph documentation.

---

<div class="post-metadata">

**Author:** ![itati01](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/itati01/32/882_2.png) [@itati01](https://igraph.discourse.group/u/itati01)\
**Post date:** [27 November 2022 07:54 UTC](https://igraph.discourse.group/t/computation-time-of-distances-significantly-increases-with-edge-weights/1424/4 "2022-11-27T07:54:03Z")

</div>

Thanks for the explanation and pointing to the doucmentation and the complexities!