rnetwork-programmingigraphundirected-graph

How do I find the shortest path from each node to any other specific node using R programming language in undirected graph?


Given a list of undirected and unweighted edges in an R dataframe(called edges_df, in which each row of the data frame contains id, start_x, end_x, start_y, end_y); how do I find the shortest path from each node to any specific node, say node 3(node with id=3) which is found in another data frame(called nodes_df) of nodes which has id, x_value, and y_value as it's columns, when travelling across the network edges. To make it easier, I attach below R code for creating the dataframes and screenshot of the dataframes.

edges_df <- data.frame(
id=c(1,2,3,4,5,6,7,8,9,10), 
start_x=c(46646.8,46646.8,46680.2,46680.2,46713.5,46713.5,46713.5,46662.2,46662.2,46662.2), end_x=c(46646.8,46680.2,46780.5,45723.5,46813.5,46813.5,46962.2,47662.2,46662.2,44879.4), 
start_y= c(7392.8, 7392.8,7459.4,7659.4,7659.4,7852.3, 7182.7, 7143.9, 7243.9, 7899.5), 
end_y= c(7412.8, 7536.2,7346.2,7642.5, 7642.5, 7271.3,7653.7,7392.8,7921.4,7392.8)
                       )

nodes_df <- data.frame(
id=c(1,2,3,4,5), 
x_value= c(46728.9,46970.9,45236.9, 47852.9, 50123.9), 
y_value= c(7463.89,7563.89,7417.89,7417.89,7407.89)
                     )

edges_df

enter image description here

nodes_df

enter image description here


Solution

  • For example:

    library(igraph)
    g <- make_ring(6)
    specific <- 3
    distances(g, to=specific)
    ##      [,1]
    ## [1,]    2
    ## [2,]    1
    ## [3,]    0
    ## [4,]    1
    ## [5,]    2
    ## [6,]    3
    
    

    This gives a matrix with all the distances from any node to a chosen node.

    ?distances shows the relevant documentation.