Get subgraph of shortest path between n nodes

Question

I have an unweighted graph and I want to get a subgraph that has just the nodes and edges that contain the shortest paths between n known nodes. In this case 3 nodes (11, 29, & 13 are the names).

Question

How can I get a subgraph of shortest path between n nodes in R?

MWE

library(ggraph)
library(igraph)

hs <- highschool[highschool$year == '1958',]
set.seed(11)
graph <- graph_from_data_frame(hs[sample.int(nrow(hs), 60),])


# plot using ggraph
ggraph(graph, layout = 'kk') + 
    geom_edge_fan() + 
    geom_node_text(aes(label = name)) 

Desired Output

The desired output would be the following green subgraph (Or close, I'm eyeballing the graph above and visually picking out what would be the subgraph) ignoring/removing the other nodes and edges.

Answer 1

You can't find the shortest path between n nodes. Since the shortest path is defined only between two nodes.

I think you want shortest path from 1 node to other n-1 node you can use
get_all_shortest_paths(v, to=None, mode=ALL) from igraph library.

• v - the source for the calculated paths
• to - a vertex selector describing the destination for the calculated paths. This can be a single vertex ID, a list of vertex IDs, a single vertex name, a list of vertex names. None means all the vertices.
• mode - the directionality of the paths. IN means to calculate incoming paths, OUT mean to calculate outgoing paths, ALL means to calculate both ones.

Returns: all of the shortest path from the given node to every other reachable node in the graph in a list.
get_all_shortest_paths

So, now you have to create a graph from a list of the shortest paths.

1. Initialize an empty graph then add all path to it from the list of the path
   adding path in graph

   OR

2. make a graph for every shortest path found and take graphs union.
   union igraph