shortest.paths {igraph} | R Documentation |

`shortest.paths`

calculates the length of all the
shortest paths from or to the vertices in the
network. `get.shortest.paths`

calculates one shortest path (the
path itself, and not just its length) from or to the given vertex.

shortest.paths(graph, v=V(graph), mode = c("all", "out", "in"), weights = NULL) get.shortest.paths(graph, from, to=V(graph), mode = c("all", "out", "in"), weights = NULL) get.all.shortest.paths(graph, from, to = V(graph), mode = c("all", "out", "in")) average.path.length(graph, directed=TRUE, unconnected=TRUE) path.length.hist (graph, directed = TRUE, verbose = igraph.par("verbose"))

`graph` |
The graph to work on. |

`v` |
Numeric vector, the vertices from or to which the shortest paths will be calculated. |

`mode` |
Character constant, gives whether the shortest paths to or
from the given vertices should be calculated for directed graphs. If
`out` then the shortest paths from the vertex, if
`in` then to it will be considered. If `all` , the
default, then the corresponding undirected graph will be used,
ie. not directed paths are searched. This argument is ignored for
undirected graphs. |

`weights` |
Possibly a numeric vector giving edge weights. If this
is `NULL` and the graph has a `weight` edge attribute,
then the attribute is used. If this is `NA` then no weights are
used (even if the graph has a `weight` attribute). |

`from` |
Numeric constant, the vertex from or to the shortest paths will be calculated. Note that right now this is not a vector of vertex ids, but only a single vertex. |

`to` |
Numeric vector, only the shortest paths to these vertices will be calculated. Defaults to all vertices. |

`directed` |
Whether to consider directed paths in directed graphs, this argument is ignored for undirected graphs. |

`unconnected` |
What to do if the graph is unconnected (not
strongly connected if directed paths are considered). If TRUE only
the lengths of the existing paths are considered and averaged; if
FALSE the length of the missing paths are counted having length
`vcount(graph)` , one longer than the longest possible geodesic
in the network. |

`verbose` |
Logical scalar, whether to draw a progress meter while the calculation is running. |

The shortest paths (also called geodesics) are calculated by
using breath-first search in the graph. If no edge weights were
specified, then a breadth-first search is used to calculate the
shortest paths. If edge weigths are given and all of them are
non-zero, then Dijkstra's algorithm is used. Otherwise the
Bellman-Ford algorithm is used for `shortest.paths`

.

Please do NOT call `get.shortest.paths`

and
`get.all.shortest.paths`

with negative edge weights, it will not
work, these functions do not use the Belmann-Ford algotithm.

Note that `shortest.paths`

is able to calculate the path length
from or to many vertices at the same time, but
`get.shortest.paths`

works from one source only. This might
change in the future.

Also note that `get.shortest.paths`

gives only one shortest path,
however, more than one might exist between two vertices.

`get.all.shortest.paths`

calculates all shortest paths from a
vertex to other vertices given in the `to`

argument.

`path.length.hist`

calculates a histogram, by calculating the
shortest path length between each pair of vertices. For directed
graphs both directions are considered, so every pair of vertices
appears twice in the histogram.

For `shortest.paths`

a numeric matrix with `vcount(graph)`

columns and `length(v)`

rows. The shortest path length from a vertex to
itself is always zero. For unreachable vertices `Inf`

is included.

For `get.shortest.paths`

a list of length
`vcount(graph)`

. List element `i`

contains the vertex ids on
the path from vertex `from`

to vertex `i`

(or the other way
for directed graphs depending on the `mode`

argument). The vector
also contains `from`

and `i`

as the first and last
elements. If `from`

is the same as `i`

then it is only
included once. If there is no path between two vertices then a
numeric vector of length zero is returned as the list element.

For `get.all.shortest.paths`

a list is returned, each list
element contains a shortest path from `from`

to a vertex in
`to`

. The shortest paths to the same vertex are collected into
consecutive elements of the list.

For `average.path.length`

a single number is returned.

`path.length.hist`

returns a named list with two entries:
`res`

is a numeric vector, the histogram of distances,
`unconnected`

is a numeric scalar, the number of pairs for which
the first vertex is not reachable from the second. The sum of the two
entries is always *n(n-1)* for directed graphs and *n(n-1)/2*
for undirected graphs.

Gabor Csardi csardi@rmki.kfki.hu

West, D.B. (1996). *Introduction to Graph Theory.* Upper
Saddle River, N.J.: Prentice Hall.

g <- graph.ring(10) shortest.paths(g) get.shortest.paths(g, 5) get.all.shortest.paths(g, 0, 5:7) average.path.length(g) ## Weighted shortest paths el <- matrix(nc=3, byrow=TRUE, c(0,1,0, 0,2,2, 0,3,1, 1,2,0, 1,4,5, 1,5,2, 2,1,1, 2,3,1, 2,6,1, 3,2,0, 3,6,2, 4,5,2, 4,7,8, 5,2,2, 5,6,1, 5,8,1, 5,9,3, 7,5,1, 7,8,1, 8,9,4) ) g2 <- add.edges(graph.empty(10), t(el[,1:2]), weight=el[,3]) shortest.paths(g2, mode="out")

[Package *igraph* version 0.5.1 Index]