Shortest Path Related Functions

get_shortest_paths() returns a single shortest path per vertex pair, while the variant with _all_ returns all found paths. The variant with _simple_ removes paths with cycles. The results should be the same for simple graphs like trees, but the order of the paths may differ.

Usage

get_shortest_paths(
  graph,
  from,
  to = integer(0L),
  weights = numeric(0L),
  mode = 3L
)

get_all_shortest_paths(
  graph,
  from,
  to = integer(0L),
  weights = numeric(0L),
  mode = 3L
)

get_all_simple_paths(graph, from, to = integer(0L), cutoff = -1L, mode = 3L)

Source

https://igraph.org/c/doc/igraph-Structural.html#shortest-path-related-functions

Arguments

graph

An igraph_ptr object.

from

An integer vector of vertex IDs.

to

An integer vector of vertex IDs.

weights

A numeric vector of edge weights; TRUE to use Eattr(graph, "weight").

mode

An integer value of edge type to count; {1: OUT, 2: IN, 3: ALL}.

cutoff

integer

Value

A list of integer IDs of vertices in the paths.

Examples

g = graph_tree(5L)
vsource = Vsource(g)
vsink = Vsink(g)
get_shortest_paths(g, vsource, vsink, mode = 1L)
#> [[1]]
#> [1] 1 3
#> 
#> [[2]]
#> [1] 1 2 4
#> 
#> [[3]]
#> [1] 1 2 5
#> 
get_all_shortest_paths(g, vsource, vsink, mode = 1L)
#> [[1]]
#> [1] 1 3
#> 
#> [[2]]
#> [1] 1 2 4
#> 
#> [[3]]
#> [1] 1 2 5
#> 
get_all_simple_paths(g, vsource, vsink, mode = 1L)
#> [[1]]
#> [1] 1 2 4
#> 
#> [[2]]
#> [1] 1 2 5
#> 
#> [[3]]
#> [1] 1 3
#>