R igraph: Fast shortest path

Question

I'm writing a script to calculate shortest paths between 352k pairs of 983 nodes, for which I'm currently using igraph's shortest.paths function. It currently takes around 35 seconds, which isn't practical for my application - I'd ideally need it down to around 5 seconds but I'm not sure if this is feasible.

The main inefficiency of shortest.paths that I can think of is that it's calculating shortest paths for every single possible node pair (all 966k).

Does anyone know of a faster way of doing this (including any reasonable pre-processing I could do, or a way of getting the algorithm to only run on the node pairs I need it for?

Thanks

Example

set.seed(1)
nodes <- c(1:1000)
edgelist <- expand.grid(nodes,nodes) %>%
  mutate(weight = runif(nrow(.))) %>%
  arrange(weight) %>%
  slice(1:350000)

graph <- edgelist %>%
  select(c(1,2)) %>%
  as.matrix(.) %>%
  graph_from_edgelist(., directed = F)

graph <- set.edge.attribute(graph, "weight", index=E(graph), edgelist$weight)

start <- Sys.time()
s.paths <- shortest.paths(graph,
                          algorithm = "dijkstra")
Sys.time() - start

Runtime: 18s

In this example, I only actually want the 350k node-pairs in the edgelist, but it's calculating all 1 million possible pairs. I can extract the ones I want easily, but I'm wondering whether I can get the run time down by somehow getting it to only calculate the distances for the pairs I actually need (or by any other means).

Answer 1

Here shortest.paths is equivalent to distances, which yields a matrix (type ?distances to see the examples there)

For you solution, you could use diag like below to retrieve the three distances you are after:

diag(s.paths)