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

,

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)

``````# 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)
``````

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

1 Like

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.

1 Like

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