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,
  ...,
  weights = numeric(0L),
  from = integer(0L),
  to = integer(0L),
  mode = 3L
)

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

get_all_simple_paths(
  graph,
  from,
  to = integer(0L),
  mode = 3L,
  minlen = -1L,
  maxlen = -1L,
  max_results = -1L
)

Source

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

Arguments

graph

An igraph_ptr object.

...

Unused, but temporarily included to avoid silent bugs and to prompt users to cope with breaking changes in version 1.0.

weights

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

from

An integer vector of vertex IDs.

to

An integer vector of vertex IDs.

mode

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

minlen

Minimum length of paths to be considered. Unlimited if negative.

maxlen

Maximum length of paths to be considered. Unlimited if negative.

max_results

At most this many paths will be recorded. Unlimited if negative.

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, from = vsource, to = vsink, mode = 1L)
#> [[1]]
#> [1] 1 3
#> 
#> [[2]]
#> [1] 1 2 4
#> 
#> [[3]]
#> [1] 1 2 5
#> 
get_all_shortest_paths(g, from = vsource, to = vsink, mode = 1L)
#> [[1]]
#> [1] 1 3
#> 
#> [[2]]
#> [1] 1 2 4
#> 
#> [[3]]
#> [1] 1 2 5
#> 
get_all_simple_paths(g, from = vsource, to = vsink, mode = 1L)
#> [[1]]
#> [1] 1 2 4
#> 
#> [[2]]
#> [1] 1 2 5
#> 
#> [[3]]
#> [1] 1 3
#>