0

I am trying to find out the shortest path on this project that I am working on and nothing pops up. I was wondering if I could get any help from here, thanks! The link below leads to my code, I appreciate any help! It works when i try to find 1 to 14 but when i try 1 to 165, it just doesn't work. i really need your help. I have over 165 vertices and I didn't include it in this because the post looks like it is mostly code.

library(igraph)



graph <- list("1"=c("14"),
          "2"=c("3"),            
          "3"=c("2","9","15"),

weights <- list("1"=c(220),
          "2"=c(70),
          "3"=c(70,40,30),


G <- data.frame(stack(graph), weights = stack(weights)[[1]])

set.seed(500)
el <- as.matrix(stack(graph))
g <- graph_from_edgelist(el)

oldpar <- par(mar = c(1, 1, 1, 1))
plot(g, edge.label = stack(weights)[[1]], vertex.size = 5, edge.width 
= 2, edge.arrow.size = 0.2, edge.label.cex = 0.4, vertex.label.cex = 
0.6)
par(oldpar)
#####
path_length <- function(path) {

  if (is.null(path)) return(Inf)


  pairs <- cbind(values = path[-length(path)], ind = path[-1])
  sum(merge(pairs, G)[ , "weights"])
}
find_shortest_path <- function(graph, start, end, path = c()) {

  if (is.null(graph[[start]])) return(NULL)

  path <- c(path, start)


  if (start == end) return(path)




shortest <- NULL
  
  for (node in graph[[start]]) {
    
    if (!(node %in% path)) {
      
      newpath <- find_shortest_path(graph, node, end, path)
     
      if (path_length(newpath) < path_length(shortest))
        shortest <- newpath
    }
  }
  
  shortest
}
  find_shortest_path(graph, "1", "165")
Phil
  • 7,287
  • 3
  • 36
  • 66
ja peyk
  • 1
  • 1
  • Please don't link to external documents with code. Edit your question to include a reproducible example including code and any data required to run it - it makes it much easier to help. – nrennie Jun 12 '23 at 14:22
  • 1) Create an edgelist that has the columns `from`, `to`, `weight`; 2) use `igraph::graph_from_dataframe()` to create an `igraph` object; 3) use `igraph::shortest_paths()` to get shortest paths. If you expect more help here, please do what nrennie suggests in their comment; see [here](https://stackoverflow.com/questions/5963269/how-to-make-a-great-r-reproducible-example) to learn how to create a reproducible example to include in your question. – Till Jun 12 '23 at 17:53

0 Answers0